##### Updated on July 11, 2017

### Context

Depth-first search (DFS) is a common searching algorithm for graphs, alongside Breadth-first search (BFS).

DFS is useful for finding ways to solve mazes. It is also a vital ingredient for topological sorting.

The key characteristic of DFS is that it is *recursive* in nature, thus a **stack** becomes very useful when defining the algorithm.

### The algorithm

```
def dfs(parent, vertex):
for neighbor in vertex:
if neighbor not in parent:
parent[neighbor] = vertex
dfs(parent, vertex)
```

The pseudocode above represents the core algorithm of depth-first search.

Inputs:

**parent**: A hash-table (or dictionary) that stores a vertices as keys, and their respective parents as values.**vertex**: The vertex that we are currently evaluating.

Strategy:

The idea of this 4-liner algorithm is that we check the adjacencies (neighbors) of a vertex.

If we find new neighbors that we haven't visited before, then we want to record this neighbor in our `parent`

dictionary. We don't particularly care for *old* neighbors, i.e. neighbors that are already recorded in our `parent`

dictionary, because it will cost us a good chunk of performance for nothing.

We record the neighbor as a key in the dictionary and set its value to the neighbor's parent, which would be `vertex`

. Because these neighbors are adjacent nodes to `vertex`

, it makes sense that the `vertex`

is the parent, and the neighbors are its children.

The last thing to do after recording the neighbor is to do another function call to itself: `dfs(vertex)`

. We are going *depth-first*, so if you envision a graph as a tree, we will keep traversing down this branch before even considering other neighbors at the current level of the tree.

### The high level view

The latter algorithm is appealing because it is short, concise, and effective. However, it begs the question of *where or how do we start?*

The best way to do this is to define our variables properly.

If we have a graph, then that means we should have a set of *vertices* that represent the graph.

i.e. `nodes = [A, B, C, D, E]`

We should also have our *edges* defined somewhere. Edges are best defined in an *adjacency list*, which should be used to represent the neighbors of a vertex.

### Starting Point

Once we have our vertices defined, we can now define an algorithm that accounts for all vertices in the highest-level view so that all nodes and edges in the graph are accounted for.

```
def dfs-top(nodes):
parent = {}
for node in nodes:
if node not in parent:
# we're starting at the top-level of a graph, so no `parent` per se
parent[node] = None
dfs(parent, node)
```

Inputs:

**nodes**: An array (or list) of vertices

Strategy:

`dfs-top`

is a function that starts the entire process of DFS in a graph.

We declare the `parent`

dictionary here for the first time, which will be passed into the recursive `dfs`

function calls.

By iterating through each vertex, we can guarantee that every vertex in the graph is given a chance to recursively go through its neighbors (via `dfs(parent, node)`

).

If the current vertex we are evaluating has never been visited before, we mark it in the `parent`

dictionary and set its value to be `None`

. The `None`

may be a bit misleading here, but the reason why it is marked `None`

is because:

- In the highest-level view, we can't distinguish a vertex as a parent of some other vertex.
- We are iterating through all vertices available, so there is no concept of a
*parent*

In contrast to the `dfs`

function, the concept of a *parent* is clear because we are checking the *neighbors* of some given vertex.

### Topological Sort

Topological sort is a directed acyclic (no cycles) graph ordering that sorts based on the property that *u* comes before *v* when there is a directed edge from *u* that points to *v*.

Implementing DFS gives us a way to do a topological sort on a graph. Simply put, it is the *reverse* of the timing that the vertices finish in the recursive DFS stack.

We can modify our DFS algorithm above to account for this.

First we'll define some global `stack`

list. Python Lists can be used very much like stacks with its *append/pop* that are synonymous to a Stack data structure's *push/pop*.

```
stack = [] # a stack defined in the global scope, for demonstration
```

Then in the recursive `dfs`

function, we'll return the vertex that is *finished* (where the downward tree traversal ends) and we'll push that to our stack.

```
def dfs(parent, vertex):
for neighbor in vertex:
if neighbor not in parent:
parent[neighbor] = vertex
stack.append(dfs(parent, vertex))
return vertex
```

After `dfs-top`

runs, the global `stack`

list will have all the nodes visited, except the starting node. This starting node should be the only node in the `visited`

dictionary that does not have a value.

Once we add that starting node to our global stack, all you have to do is **reverse** the stack list.

```
stack.reverse()
```

This will give you a list of graph nodes that are **topologically sorted**.

### Conclusion

With `V = number of vertices`

and `E = number of edges`

, the worst case performance of DFS is:

$$ O(|V| + |E|) $$
This is linear time because it is linear in the size of the graph. The worst case space complexity is \(O(|V|)\) because we are keeping track of each vertex entry in our `parent`

dictionary above, and the size of our dictionary at its largest will have all the vertex keys in the graph.

There are numerous ways to implement DFS. For example, you can actually make use of a stack data structure, and use *iterative* code instead of *recursive* code. The entirety of DFS could also be implemented in one function, rather than splitting its logic into two like I have done here.

With that said however, there is something sweet and beautiful about having a nice search algorithm like DFS be written in 4 lines of code. I also feel that the distinction between the two functions `dfs`

and `dfs-top`

is disparate enough and it is a nice way of categorizing or mincing the logic of DFS into sub-components.

*References*