Why an Explicit Stack Needs More Than Vertices
Recursive depth-first search (DFS) suspends a call whenever it starts exploring a newly discovered neighbor. When that call finishes, the earlier call resumes at the next neighbor in its adjacency list. An explicit stack can reproduce this behavior, but only if it stores enough information to resume each suspended search. A stack containing just vertices does not, by itself, record where each suspended call should continue.
Throughout, graphs are finite and simple. The examples are directed: an arc \(u\to v\) allows DFS to go from \(u\) to \(v\), but not necessarily from \(v\) to \(u\). Each vertex has a fixed ordered adjacency list, and DFS processes its neighbors in that order. The list order is part of the input to the trace: changing it can change the DFS tree and the discovery and finishing orders.
For an explicit-stack implementation, a frame is a pair \((u,i)\): \(u\) is a currently active vertex, and \(i\) is the position of the next neighbor of \(u\) to inspect. Frames are kept from bottom to top, with the top frame representing the recursive call currently being executed. When that call finds a white neighbor, the algorithm advances its position and pushes a new frame for the neighbor. When a frame has no neighbors left to inspect, it is popped and its vertex is finished.
Advancing the parent frame before pushing the child is important: it records exactly where the parent call must resume after the child finishes. A frame for a vertex with no neighbors starts with next position \(1\), which is already past the end of its list, so it is immediately finished. Gray and black neighbors are both ignored for discovery; their colors still distinguish active vertices from completed ones.
A Frame-by-Frame Trace
Worked Example: Matching Recursive DFS on a Directed Graph
Let \(G=(V,E)\) be the directed graph with \(V=\{r,a,b,c,d\}\) and \(E=\{r\to a,r\to b,a\to b,a\to c,a\to d,b\to c,b\to d,c\to r,c\to d,d\to a\}\). Use the adjacency lists \(r:[a,b]\), \(a:[b,c,d]\), \(b:[c,d]\), \(c:[r,d]\), \(d:[a]\), and start at \(r\). In the table, stacks are written bottom to top; a frame \((u,i)\) gives the next position to inspect.
| Step | Action | Stack afterward |
|---|---|---|
| 1 | Discover \(r\); push \((r,1)\). | \((r,1)\) |
| 2 | Inspect \(r\)'s position 1, \(a\). Advance \(r\); \(a\) is white, so discover it, set parent \(r\), and push it. | \((r,2),(a,1)\) |
| 3 | Inspect \(a\)'s position 1, \(b\). Advance \(a\); \(b\) is white, so discover it, set parent \(a\), and push it. | \((r,2),(a,2),(b,1)\) |
| 4 | Inspect \(b\)'s position 1, \(c\). Advance \(b\); \(c\) is white, so discover it, set parent \(b\), and push it. | \((r,2),(a,2),(b,2),(c,1)\) |
| 5 | Inspect \(c\)'s position 1, \(r\). Advance \(c\); \(r\) is gray, so do not push it. | \((r,2),(a,2),(b,2),(c,2)\) |
| 6 | Inspect \(c\)'s position 2, \(d\). Advance \(c\); \(d\) is white, so discover it, set parent \(c\), and push it. | \((r,2),(a,2),(b,2),(c,3),(d,1)\) |
| 7 | Inspect \(d\)'s position 1, \(a\). Advance \(d\); \(a\) is gray, so do not push it. | \((r,2),(a,2),(b,2),(c,3),(d,2)\) |
| 8 | \(d\) has no more neighbors. Finish \(d\) and pop its frame. | \((r,2),(a,2),(b,2),(c,3)\) |
| 9 | \(c\) has no more neighbors. Finish \(c\) and pop its frame. | \((r,2),(a,2),(b,2)\) |
| 10 | Inspect \(b\)'s position 2, \(d\). Advance \(b\); \(d\) is black, so do not push it. | \((r,2),(a,2),(b,3)\) |
| 11 | \(b\) has no more neighbors. Finish \(b\) and pop its frame. | \((r,2),(a,2)\) |
| 12 | Inspect \(a\)'s position 2, \(c\). Advance \(a\); \(c\) is black, so do not push it. | \((r,2),(a,3)\) |
| 13 | Inspect \(a\)'s position 3, \(d\). Advance \(a\); \(d\) is black, so do not push it. | \((r,2),(a,4)\) |
| 14 | \(a\) has no more neighbors. Finish \(a\) and pop its frame. | \((r,2)\) |
| 15 | Inspect \(r\)'s position 2, \(b\). Advance \(r\); \(b\) is black, so do not push it. | \((r,3)\) |
| 16 | \(r\) has no more neighbors. Finish \(r\) and pop its frame. | empty |
The discovery order is \(r,a,b,c,d\), and the finishing order is \(d,c,b,a,r\). The parent edges are \(r\to a\), \(a\to b\), \(b\to c\), and \(c\to d\). In particular, discovery is not the same as the order in which vertices are popped: \(a\) is discovered second but finishes fourth.
Check: The listed parent edges follow the exact white-neighbor steps in the trace. Each vertex is discovered once, and the finishing order is the reverse of the nested active-call order: \(d\) finishes before \(c\), \(c\) before \(b\), \(b\) before \(a\), and \(a\) before \(r\).
Why the Frame Algorithm Preserves the Recursive Trace
Proof. We compare the two procedures operation by operation. At any moment, maintain the following invariant: the vertices on the explicit stack, from bottom to top, are exactly the active recursive calls, from oldest to newest; for each such vertex \(u\), its frame position is the next neighbor that the recursive call for \(u\) would inspect. The gray vertices are exactly these active calls. Both procedures have discovered the same vertices, assigned the same parents, and finished the same vertices.
When a root is white, both procedures discover that root, make it gray, and begin with its first neighbor. The invariant therefore holds when its first frame is pushed. Suppose it holds before the next operation. If the current recursive call has no uninspected neighbors, it finishes and returns to its caller. The stack algorithm detects that the frame position is past the end of the list, makes the same vertex black, and pops the frame. The caller's frame already points to its next neighbor, so the invariant continues to hold.
Otherwise, both procedures inspect the same next neighbor \(v\), because the frame stores the recursive call's next position and both use the same adjacency order. If \(v\) is white, both set its parent to the current vertex, make it gray, and begin exploring its adjacency list before resuming the current vertex. The stack algorithm does this by pushing \((v,1)\), so the invariant is preserved. If \(v\) is gray or black, both procedures leave its discovery state and parent unchanged and continue to the following neighbor; the frame's position has already advanced, so again the invariant holds. Induction over these operations gives identical discovery and finishing behavior for the whole search from that root. When that search ends, both procedures choose the same next white root, if one exists. Applying the same argument at each such root proves the result for the full traversal. \(\square\)
This proof identifies the essential feature: the stack must preserve the suspended call's progress through its adjacency list. A stack that stores only vertices, without an equivalent way to remember the next neighbor, may not preserve the recursive order.
Why “Push Every Neighbor” Can Change the Search
Worked Example: A Push-All Stack Changes Discovery and Parents
Let \(G=(V,E)\) be directed, with \(V=\{r,a,b,c\}\) and \(E=\{r\to a,r\to b,a\to b,a\to c,b\to c\}\). The ordered adjacency lists are \(r:[a,b]\), \(a:[b,c]\), \(b:[c]\), \(c:[]\). Recursive DFS from \(r\) discovers \(a\) first, then follows \(a\to b\), and then follows \(b\to c\). Its discovery order is \(r,a,b,c\); its parent edges are \(r\to a\), \(a\to b\), \(b\to c\).
Now consider a different procedure: when a vertex is popped, scan its neighbors in reverse adjacency order, mark every white neighbor immediately when pushing it, and then continue popping. At \(r\), reverse order is \(b,a\). The procedure marks \(b\) and pushes it, then marks \(a\) and pushes it. Thus the discovery order so far is \(r,b,a\), even though \(a\) is on top of the stack and will be popped next.
| Step | Action | Stack afterward (bottom to top) | Discovery order |
|---|---|---|---|
| 1 | Mark and push root \(r\). | \(r\) | \(r\) |
| 2 | Pop \(r\). In reverse list order, mark and push \(b\), then mark and push \(a\). | \(b,a\) | \(r,b,a\) |
| 3 | Pop \(a\). Its neighbors in reverse order are \(c,b\). Mark and push \(c\); skip \(b\), which is already gray. | \(b,c\) | \(r,b,a,c\) |
| 4 | Pop \(c\); it has no neighbors. | \(b\) | \(r,b,a,c\) |
| 5 | Pop \(b\). Its neighbor \(c\) is no longer white, so do not push it. | empty | \(r,b,a,c\) |
The push-all procedure has parent edges \(r\to b\), \(r\to a\), and \(a\to c\), unlike recursive DFS. Its discovery order \(r,b,a,c\) also differs from recursive DFS's \(r,a,b,c\). Marking a neighbor as soon as it is pushed prevents a later active vertex from discovering it through the edge recursive DFS would inspect first.
Check: In the recursive trace, \(r\to a\) is followed before \(r\to b\); while exploring \(a\), the white neighbor \(b\) becomes its child. In the push-all trace, \(b\) is already marked at \(r\), before \(a\) is popped, so \(a\) cannot discover \(b\). Both procedures may visit all four vertices, but equal reachability does not mean equal recursive semantics.
Restarting at New Roots
DFS from one root explores only vertices reachable from that root by directed paths. To obtain a DFS forest of the whole directed graph, scan all vertices in a fixed root order and start a new search at each vertex that remains white. A previously explored vertex is not revisited, even if there is an arc to it from a later root. “Connected component” is not needed for this procedure: in a directed graph, the relevant condition for discovery from a root is directed reachability.
Worked Example: A Full DFS Forest
Let \(G=(V,E)\) be directed, with \(V=\{1,2,3,4,5\}\) and \(E=\{1\to2,2\to1,3\to2,3\to4\}\). Use adjacency lists \(1:[2]\), \(2:[1]\), \(3:[2,4]\), \(4:[]\), \(5:[]\), and root order \(1,2,3,4,5\).
| Step | Action | Stack | Forest edges added |
|---|---|---|---|
| 1 | Root \(1\) is white; discover it and push its frame. | \((1,1)\) | none |
| 2 | Inspect \(1\to2\). Vertex \(2\) is white, so discover it and push it. | \((1,2),(2,1)\) | \(1\to2\) |
| 3 | Inspect \(2\to1\). Vertex \(1\) is gray; skip it. Then finish \(2\). | \((1,2)\) | \(1\to2\) |
| 4 | Vertex \(1\) has no more neighbors; finish it. The scan reaches root \(2\), already black, so it is skipped. | empty | \(1\to2\) |
| 5 | Root \(3\) is white; discover it. Inspect \(3\to2\); vertex \(2\) is black, so skip it. | \((3,2)\) | \(1\to2\) |
| 6 | Inspect \(3\to4\). Vertex \(4\) is white, so discover it and push it. Then finish \(4\), followed by \(3\). | empty | \(1\to2,3\to4\) |
| 7 | Roots \(4\) and then \(5\) are considered. Vertex \(4\) is black; discover and finish isolated vertex \(5\). | empty | \(1\to2,3\to4\) |
The forest has roots \(1,3,5\), with tree edges \(1\to2\) and \(3\to4\). The discovery order is \(1,2,3,4,5\), and the finishing order is \(2,1,4,3,5\). The arc \(3\to2\) does not add a forest edge because \(2\) was already discovered and finished in the search from \(1\).
Check: The two forest edges lead to all five vertices from their respective roots: \(1\) reaches \(2\), \(3\) reaches \(4\), and \(5\) is a root by itself. Each vertex appears exactly once in the discovery order.
Common Pitfalls and Practical Guidance
Confusing pop order with discovery order. In a push-all method, a vertex can be marked when it is pushed and popped only later. If discovery means the white-to-gray change, its position in the discovery order is when it is marked, not when it is popped. In the push-all example, \(b\) is marked before \(a\), so the discovery order begins \(r,b,a\), even though \(a\) is popped first.
Pushing neighbors in reverse order is not enough. Reversing a list can arrange the order in which vertices are popped, but it does not suspend the current vertex's search at one specific neighbor. Marking every neighbor during the push phase can claim a vertex before recursive DFS would reach it. To preserve parents and discovery order as well as eventual visitation, use frames or another representation that stores the active call's next-neighbor position.
Keep the adjacency order fixed when comparing traces. Recursive and iterative versions should be compared using the same root order and adjacency-list order. If either order changes, a different valid DFS trace may result; that is not a failure of the frame simulation.
The frame-based implementation is useful when recursion is inconvenient or unavailable, while still requiring the same search tree and event order as the recursive definition. The key test is not simply whether both versions reach the same vertices. To match recursive semantics, each white neighbor must be discovered at the moment its recursive call would begin, and each suspended search must resume at its next unprocessed neighbor.
Check Your Understanding
For each question, specify the adjacency-list order if it affects your answer.
- In the frame algorithm, why must the current frame's position advance before a child frame is pushed?
- For the graph in the first worked example, list the parent edges and explain why \(r\to b\) is not a parent edge.
- In the push-all example, which vertex is marked first after \(r\), and why is that not the recursive discovery order?
- What does the frame algorithm do when the top vertex has no neighbors left to inspect?
- In the full-forest example, why does the arc \(3\to2\) not add a tree edge?