DFS as a Sequence of Calls and Returns
Depth-first search (DFS) explores a graph by following one available edge as far as possible before returning to consider another. In its recursive form, a call for a vertex pauses while calls for its newly discovered neighbors run. Colors summarize each vertex’s progress, and timestamps record exactly when each call begins and ends. These records are useful only if the recursive order is followed carefully: a parent cannot finish while a recursive call made from it is still running.
Throughout this tutorial, graphs are finite and simple. A directed graph has edges that are ordered pairs; \(uv\) denotes the directed edge from \(u\) to \(v\). For each vertex, its outgoing neighbors are stored in a fixed order. The root vertices are also considered in a fixed order. These choices determine a particular DFS trace, so changing neighbor order can change the timestamps even when the graph is unchanged.
The clock starts at \(0\) and increases by \(1\) at each discovery and each finish. Each vertex is discovered once and finished once. The recursive procedure below makes the relevant order explicit. In the outer loop, every vertex is used as a root in the fixed root order; a root call is made only if that vertex is still white.
Change \(u\) from white to gray, increase the clock by \(1\), and record that value as its discovery time.
Consider the outgoing neighbors of \(u\) one by one in their fixed order. If the current neighbor \(v\) is white, call the procedure recursively on \(v\). If \(v\) is gray or black, do not make a recursive call for it.
Only after every outgoing neighbor has been considered and all recursive calls made from \(u\) have returned, change \(u\) from gray to black, increase the clock by \(1\), and record that value as its finish time.
A call that is waiting for a recursive call to return remains active. In an implementation, its frame retains its position in the adjacency list so that scanning resumes at the next neighbor after the recursive call returns. The active stack is the sequence of calls that have begun but have not yet returned.
The Active-Stack Invariant
Proof. Initially there are no active calls and every vertex is white, so the stack and the set of gray vertices are both empty. We check what happens whenever the stack changes. When a call begins for a white vertex \(v\), the procedure changes \(v\) to gray and places its call on top of the stack. The previous top vertex \(u\), if there is one, made this call while scanning its outgoing neighbors, so \(uv\) is a directed edge. Thus the new stack and gray set still agree, and the new top is joined to its predecessor by the edge that caused the call. When a call for \(u\) returns, all its neighbors have been scanned and all calls made from it have returned. The procedure changes \(u\) from gray to black and removes its call from the top of the stack. No other vertex changes color at that return, so the remaining stack still consists of exactly the gray vertices. Scanning an edge without making a call changes neither the stack nor any color. These are all the events that can change the stack or colors, so the statement holds throughout the execution. \(\square\)
This invariant explains the importance of the colors. White means a call has not begun; gray means a call is still pending, including a call paused while exploring a neighbor; black means the call has returned. A vertex does not become black merely because it has been discovered or because its own outgoing-neighbor list is temporarily paused.
Proof. A call begins only for a white vertex, and the first action of that call changes the vertex to gray. It cannot be called again during that run, because every later attempted call on that vertex finds it nonwhite. The call eventually finishes: each adjacency list is finite, and every recursive call is on a vertex that was white and so can be called at most once. Therefore the finite process of scanning neighbors and completing nested calls terminates. On return, the vertex changes to black. Hence each vertex has exactly one discovery and one finish. The clock increases by \(1\) for each of these \(2n\) events and never otherwise, so the assigned values, in event order, are \(1,2,\ldots,2n\), with no repetitions. A vertex’s discovery occurs when its call begins, and its finish occurs only when that call returns, so its discovery precedes its finish and \(t_{\mathrm{disc}}(v)<t_{\mathrm{fin}}(v)\). This also applies when \(n=0\): there are no calls or timestamps, and the assertion about every vertex holds vacuously. \(\square\)
Worked Traces
Worked Example: Neighbor Order Changes the Timestamps
Let the directed graph have \(V=\{p,q,r,s\}\) and \(E=\{pr,pq,rs,qs\}\). The outgoing neighbors are \(r,q\) at \(p\), \(s\) at \(r\), \(s\) at \(q\), and none at \(s\). Start at \(p\), and use the neighbor order \(r,q\) there. The clock begins at \(0\).
| Clock event | Action | Active stack afterward |
|---|---|---|
| 1 | Discover \(p\) | \(p\) |
| 2 | Discover \(r\) from \(p\) | \(p,r\) |
| 3 | Discover \(s\) from \(r\) | \(p,r,s\) |
| 4 | Finish \(s\) | \(p,r\) |
| 5 | Finish \(r\) | \(p\) |
| 6 | Discover \(q\) from \(p\) | \(p,q\) |
| 7 | Finish \(q\) | \(p\) |
| 8 | Finish \(p\) | empty |
When \(q\) scans its only outgoing neighbor \(s\), \(s\) is already black, so \(q\) makes no recursive call and then finishes. The discovery and finish times are \(t_{\mathrm{disc}}(p)=1\), \(t_{\mathrm{disc}}(r)=2\), \(t_{\mathrm{disc}}(s)=3\), \(t_{\mathrm{fin}}(s)=4\), \(t_{\mathrm{fin}}(r)=5\), \(t_{\mathrm{disc}}(q)=6\), \(t_{\mathrm{fin}}(q)=7\), and \(t_{\mathrm{fin}}(p)=8\).
Check: There are four vertices, so there must be \(2\cdot4=8\) timestamp events; the table has eight, using \(1\) through \(8\) once each. Each vertex’s discovery precedes its finish: \(1<8\) for \(p\), \(2<5\) for \(r\), \(3<4\) for \(s\), and \(6<7\) for \(q\). In particular, \(p\) cannot finish before its call on \(r\) and then its call on \(q\) have both returned.
Worked Example: A Disconnected Directed Graph
Let \(V=\{a,b,c,d,e,f\}\) and \(E=\{ab,ac,bd,cd,ef,fe\}\). Use outgoing-neighbor order \(b,c\) at \(a\), and use root order \(a,b,c,d,e,f\). After the call rooted at \(a\) finishes, the outer loop continues; vertices already black are skipped.
| Clock event | Action | Active stack afterward |
|---|---|---|
| 1 | Discover \(a\) | \(a\) |
| 2 | Discover \(b\) | \(a,b\) |
| 3 | Discover \(d\) | \(a,b,d\) |
| 4 | Finish \(d\) | \(a,b\) |
| 5 | Finish \(b\) | \(a\) |
| 6 | Discover \(c\) | \(a,c\) |
| 7 | Finish \(c\) | \(a\) |
| 8 | Finish \(a\) | empty |
| 9 | Discover \(e\) | \(e\) |
| 10 | Discover \(f\) | \(e,f\) |
| 11 | Finish \(f\) | \(e\) |
| 12 | Finish \(e\) | empty |
The edge \(cd\) is considered when \(c\) is active; \(d\) is black by then, so DFS does not call \(d\) again. The edge \(fe\) is considered while \(e\) is gray, but that also causes no recursive call. The second component is reached by the outer loop, not by a directed path from \(a\).
Check: Here \(n=6\), so the number of events is \(2\cdot6=12\), matching the table. The times are \(a:(1,8)\), \(b:(2,5)\), \(d:(3,4)\), \(c:(6,7)\), \(e:(9,12)\), and \(f:(10,11)\), where each pair lists discovery then finish. Every pair is in increasing order, and the stack is empty at the end of each root’s completed search.
Worked Example: A Recursive Call Waits for Its Descendant
Let \(V=\{x,y,z,w\}\) and \(E=\{xy,yx,xz,zw,wz\}\). Start at \(x\), with outgoing-neighbor order \(y,z\) at \(x\). At \(y\), the only outgoing neighbor is \(x\); at \(z\), it is \(w\); and at \(w\), it is \(z\).
The event sequence is: discover \(x\) at time \(1\); discover \(y\) at time \(2\); inspect \(yx\), where \(x\) is gray; finish \(y\) at time \(3\); discover \(z\) at time \(4\); discover \(w\) at time \(5\); inspect \(wz\), where \(z\) is gray; finish \(w\) at time \(6\); finish \(z\) at time \(7\); finish \(x\) at time \(8\). The inspections of \(yx\) and \(wz\) do not change the clock because only discoveries and finishes receive timestamps.
The stack at the deepest point is \(x,z,w\). While \(w\) is active, \(z\) remains active beneath it, and while \(z\) is active, \(x\) remains active beneath it. Thus the return order must be \(w,z,x\), not \(z,w,x\).
Check: Four vertices produce \(2\cdot4=8\) timestamp events. The resulting pairs are \(x:(1,8)\), \(y:(2,3)\), \(z:(4,7)\), and \(w:(5,6)\). Each discovery time is smaller than the corresponding finish time, and all eight clock values occur exactly once.
Common Mistakes and Why the Invariant Matters
Finishing a parent too early. In the first example, after \(s\) finishes at time \(4\), the call for \(r\) returns at time \(5\), but \(p\) is still active. It must continue scanning its neighbor \(q\). The correct continuation is: discover \(q\) at \(6\), finish \(q\) at \(7\), then finish \(p\) at \(8\). An incorrect trace might write “finish \(p\) at \(6\), discover \(q\) at \(7\), finish \(q\) at \(8\).” That violates the procedure: \(p\) cannot finish before its outgoing neighbors have been considered, and \(q\) must be called from \(p\) before \(p\) returns.
Counting only discoveries. A graph with \(n\) vertices has \(n\) discovery events, but it also has \(n\) finish events. Thus its complete DFS timestamp sequence has \(2n\) events, not \(n\). In the four-vertex first example, recording only discovery values \(1,2,3,4\) omits the returns and cannot describe when nested calls finish. The clock must increase at both kinds of event.
Treating every examined edge as a call. DFS recursively calls a neighbor only when that neighbor is white. In the third example, \(y\) sees gray \(x\), and \(w\) sees gray \(z\); neither inspection creates another call. Similarly, in the first example \(q\) sees black \(s\). A nonwhite neighbor is not recursively entered again.
These rules are useful when checking a hand trace or debugging recursive code. At any moment, the gray vertices identify the calls that have not returned; the stack order tells which vertex must finish next. At the end of the search, every vertex is black, even in a disconnected graph, because the outer loop starts a new call at each still-white vertex.
Check Your Understanding
For each question, specify the root and neighbor orders if a trace depends on them.
- In a DFS call, what does gray mean, and how does it differ from black?
- Why does a recursive call on a white neighbor remain on the stack while that neighbor is explored?
- For the graph in the first worked example, reverse the order of \(p\)'s neighbors to \(q,r\). Trace the events and compute all eight timestamps.
- In the second worked example, why is a new root call needed for \(e\), and why is \(d\) not called again from \(c\)?
- A proposed trace of a graph with five vertices contains nine timestamp values. What event has necessarily been omitted, and how many values should a complete trace contain?