Iterative DFS with stack-based graph traversal (2024)

Summary

Depth-first search (DFS) on a graph (binary tree or otherwise) is most often implemented recursively, but there are occasions where it may be desirable to consider an iterative approach instead. Such as when we may be worried about overflowing the call stack. In such cases it makes sense to rely on implementing DFS with our own stack instead of relying on our program's implicit call stack. But doing so can lead to some problems if we are not careful. Specifically, as noted in another blog post, it is easy to fall into the trap of using a stack haphazardly and conducting a graph search that is not truly DFS. The issue may go undetected in some problems, but algorithms that rely on a true DFS may fail (e.g., Kosaraju's and Tarjan's algorithms for finding strongly connected components). The linked blog post above is very effective at pointing out the potential issues, but it's quite terse in its treatment. Thus, the linked blog post has been reproduced below for ease of reference (unaltered). This blog post is primarily intended to further explore the reproduced blog post below (with working Python code). TLDRLook at the graph below. If we start a DFS at vertex S, then we may visit either of the following vertices next: A or C. If we visit A from S, then our DFS should naturally lead us to visit either vertex B or vertex D next (we don't go back to vertex S because it's already been visited). If, however, we visit vertex C, then our DFS should naturally lead us to visit either vertex D or vertex F next.This is not what happens in the (flawed) stack-based traversal. Instead, from vertex S, we end up visiting vertex A and then vertex C, which is not a valid DFS. Consider the following graph: We can represent this graph in code as an adjacency list of index arrays, where vertex S maps to index 0 and vertices A, B, C, ... map to indices 1, 2, 3, ... , respectively (we'll use uppercase notation for the vertices throughout this post despite the figures depicting the vertices...