Depth-First Search, in depth: a frame-by-frame trace, the parenthesis and white-path theorems, and DFS as a hook framework

The recursion, the colours and the clock

Each vertex has a colour. White means not yet discovered, grey means discovered but not finished (it is on the recursion stack), black means finished. A global counter ticks once on every discovery and once on every finish, so on a graph with n vertices the clock runs from 1 to 2n.

The version below takes three optional hooks. on_enter(u) runs at discovery (pre-order), on_edge(u, v, kind) runs for every edge examined, and on_exit(u) runs at finish (post-order). Everything later on this page is just a choice of hooks.

WHITE, GREY, BLACK = 0, 1, 2

def dfs(graph, on_enter=None, on_edge=None, on_exit=None, order=None):
    """graph: dict vertex -> list of successors. Returns (d, f, parent)."""
    colour = {v: WHITE for v in graph}
    d, f, parent = {}, {}, {}
    clock = 0

    def visit(u):
        nonlocal clock
        clock += 1; d[u] = clock; colour[u] = GREY
        if on_enter: on_enter(u)
        for v in graph[u]:
            if colour[v] == WHITE:
                kind = "tree"; parent[v] = u
            elif colour[v] == GREY:
                kind = "back"                    # v is an ancestor still on the stack
            elif d[u] < d[v]:
                kind = "forward"                 # v is a finished descendant
            else:
                kind = "cross"                   # v finished in an earlier branch
            if on_edge: on_edge(u, v, kind)
            if kind == "tree":
                visit(v)
        colour[u] = BLACK
        clock += 1; f[u] = clock
        if on_exit: on_exit(u)

    for s in (order or graph):
        if colour[s] == WHITE:
            parent[s] = None
            visit(s)
    return d, f, parent

Cost: every vertex is entered once and every adjacency list is scanned once, so the run is O(V + E) time with adjacency lists. Memory is O(V) for the colour, time and parent maps plus the recursion stack, whose depth is the length of the longest tree path, up to V.

Frame by frame: one run on six vertices

The graph has edges A to B, A to C, A to D, B to C, C to A, D to C, E to D and E to F. Adjacency lists are in alphabetical order and the outer loop also visits vertices alphabetically. Each row below is one frame of the animation: what happened, what the recursion stack holds afterwards, and the clock.

Two things to notice. First, the forest has two trees, rooted at A and at E, because nothing reachable from A leads to E. Second, edge kinds depend on the visiting order. If D were listed before B in A's adjacency list, D to C would become a tree edge, A to C would still be a forward edge, and B to C would turn into a cross edge. The clock is a property of one run, not of the graph, so algorithms built on it rely only on facts that hold for every run. The next two sections are those facts.

The parenthesis theorem

Parenthesis theorem. For any two vertices u and v, exactly one of these holds: the intervals [d[u], f[u]] and [d[v], f[v]] are disjoint, and neither vertex is a descendant of the other in the DFS forest; or [d[v], f[v]] lies entirely inside [d[u], f[u]] and v is a descendant of u; or the reverse. Write an opening bracket at each discovery and a closing bracket at each finish and you get a well-formed string, which is where the name comes from. In the trace: (A (B (C C) B) (D D) A) (E (F F) E).

Proof. Suppose d[u] < d[v]. If d[v] < f[u], v was discovered while u was grey, so u was on the recursion stack and v was entered from somewhere above it on that stack, which makes v a descendant of u. A call returns before its caller does, so v finishes before u: f[v] < f[u] and the intervals nest. Otherwise d[v] > f[u], u was already finished when v was discovered, and the intervals are disjoint. No vertex can be a descendant of one discovered after it finished, so neither is an ancestor of the other. Swapping u and v covers d[v] < d[u].

Why you care: the theorem turns ancestry questions into two integer comparisons. d[u] <= d[v] and f[v] <= f[u] answers 'is v in u's subtree?' in O(1) after one O(V + E) pass. Euler-tour techniques for subtree sums and lowest-common-ancestor queries on trees are built on exactly this.

The white-path theorem

White-path theorem. In a DFS forest, v becomes a descendant of u if and only if, at the moment u is discovered, there is a path from u to v consisting entirely of white vertices.

Proof sketch. If v is a descendant, every vertex on the tree path from u to v was discovered after u, so all were white at d[u]. Conversely, suppose a white path exists but some vertex on it does not become a descendant, and let w be the first such vertex. Its predecessor on the path, x, is a descendant (or u itself), so f[x] <= f[u]. Since w was white at d[u] it is discovered after u, and it must be discovered before x finishes, because x scans the edge to w and would otherwise discover w itself. So d[u] < d[w] < f[x] <= f[u], and by the parenthesis theorem w's interval nests inside u's: w is a descendant. Contradiction.

This is the theorem doing the heavy lifting in two well-known results. A directed graph has a cycle if and only if DFS finds a back edge: take the first vertex u of a cycle to be discovered; the rest of the cycle is a white path, so its predecessor on the cycle becomes a descendant and the edge back to u is examined while u is grey. And in Kosaraju's algorithm, the vertex with the largest finish time lies in a source component of the condensation, which is why the second pass on the transposed graph peels off one strongly connected component at a time.

DFS as a framework: three hooks

With the theorems in hand, a whole family of algorithms becomes a few lines of hook code on top of dfs. Topological order is reverse finish order; a back edge means there is no such order:

def topo_order(graph):
    out = []
    def edge(u, v, kind):
        if kind == "back":
            raise ValueError(f"cycle through {u} -> {v}")
    dfs(graph, on_edge=edge, on_exit=out.append)
    return out[::-1]          # decreasing finish time

dag = {"shirt": ["tie", "belt"], "tie": ["jacket"], "belt": ["jacket"],
       "pants": ["belt", "shoes"], "shoes": [], "jacket": []}
print(topo_order(dag))
# ['pants', 'shoes', 'shirt', 'belt', 'tie', 'jacket']

Why reverse finish order works: for any edge u to v in a DAG the edge is tree, forward or cross, never back, and in all three cases f[v] < f[u]. For tree and forward edges v is a descendant; for cross edges v finished in an earlier branch. Bridges and articulation points use the same skeleton with one extra number per vertex, the low-link, updated in on_edge for back edges and in the post-order step for tree edges; reachability, connected components and flood fill only need on_enter. Undirected graphs are the one place to be careful: every edge appears twice, only tree and back edges can occur, and the edge straight back to the parent must be skipped by edge identity, not by vertex, or parallel edges are missed.

Stack depth in production

The recursive version is the clearest one to reason about and the most likely to crash. CPython's default recursion limit is 1000 frames, so a path graph of a few thousand vertices raises RecursionError. Raising it with sys.setrecursionlimit works for pure-Python recursion on CPython 3.11 and later, where Python-to-Python calls no longer consume C stack, but every frame still costs memory. On older versions, or when the recursion passes through C code, overrunning the C stack kills the process instead of raising. On the JVM the equivalent is StackOverflowError, governed by the thread stack size.

Three workable options, in order of preference for production code:

1. Convert to an explicit stack that stores (vertex, iterator) pairs, so finish times and post-order hooks stay exact. The conversion and its traps are covered in iterative DFS with an explicit stack.
2. Run the recursive version on a dedicated thread with a large stack, a common competitive-programming trick: threading.stack_size(512 * 1024 * 1024) plus a raised recursion limit in Python, or new Thread(null, task, "dfs", 1L << 29) in Java. The stack-size argument is only a hint to the JVM.
3. If you only need reachability, not finish times, push neighbours onto a plain list and pop. That is a valid traversal but not the same DFS: it visits vertices in a different order and gives you no finish clock.

Measure the actual worst case rather than guessing: the depth of DFS is the longest tree path, which on real graphs (call graphs, dependency trees, linked file systems) can be close to V.

Failure modes

• Recursion overflow on long chains. Symptom: works on test data, crashes on one customer's graph. Fix: iterative version, or a bounded-depth check that fails with a clear error.
• Marking visited at the wrong time. Marking a vertex black when it is pushed instead of when it finishes erases the grey state, so back edges become invisible and cycle detection silently returns 'no cycle'.
• Using undirected cycle logic on directed graphs. 'Seen it before means cycle' is wrong for directed graphs: a cross edge to a black vertex is not a cycle. Only grey targets are.
• Relying on one run's edge kinds. Forward and cross labels change with adjacency order. Tests that assert specific labels break when someone sorts the input differently.
• Missing disconnected parts. Calling visit(start) once covers one tree. Anything that needs the whole graph, such as a topological order or a full SCC split, needs the outer loop.
• Mutating the graph during traversal. Adding edges to a list while iterating over it gives order-dependent, sometimes infinite, behaviour. Snapshot the adjacency first.

Trade-offs

For a side-by-side view of when breadth-first order is the right tool instead, see BFS and DFS compared.

What to do next

1. Type out dfs with the three hooks and reproduce the trace table above; check your d and f values match [1,8], [2,5], [3,4], [6,7], [9,12], [10,11].
2. Swap the order of A's adjacency list and record which edge labels change and which facts (nesting, the back edge from C) do not.
3. Implement topo_order and test it on a graph with a cycle; confirm it raises rather than returning a wrong order.
4. Build Tarjan's SCC algorithm on the same hooks, then bridges and articulation points.
5. Generate a 200,000-vertex path graph and make your implementation survive it, using the iterative conversion or a large-stack thread.
6. Read topological sort to compare the DFS approach with Kahn's in-degree method.