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