DFS Tree, in depth: edge classification by colour and timestamps, the proofs behind it, and the low-links it powers

The DFS forest and its two clocks

Run DFS with a global clock. When a vertex is first reached it turns from WHITE to GRAY and gets a discovery time disc[u]. When all its outgoing edges have been examined it turns BLACK and gets a finish time fin[u]. The edge used to reach each newly discovered vertex is a tree edge, and the tree edges form a forest with one tree per restart from an undiscovered root.

The key fact is the parenthesis theorem. For any two vertices u and v, the intervals [disc[u], fin[u]] and [disc[v], fin[v]] are either disjoint or one contains the other. Containment happens exactly when one vertex is a descendant of the other in the DFS forest. The reason is that DFS finishes a vertex only after finishing everything discovered below it, so the calls nest like brackets. Two practical results follow. First, an ancestor test needs only two comparisons: u is an ancestor of v exactly when disc[u] <= disc[v] and fin[v] <= fin[u]. Second, at any moment the GRAY vertices are exactly the current root-to-vertex path, which is the recursion stack.

The white-path theorem completes the picture. v becomes a descendant of u exactly when, at the moment u is discovered, there is a path from u to v made entirely of WHITE vertices. Most correctness proofs about DFS start from this theorem.

Four edge types in directed graphs

In a directed graph, every edge u to v examined during DFS falls into exactly one of four classes. The colour of v when the edge is examined decides most of it, and timestamps settle the rest.

Cross edges always point backward in time, toward a vertex that finished before u was discovered. If v had still been WHITE when u was discovered, the white-path theorem would have made v a descendant of u, and the edge would be a tree or forward edge. So a cross edge never points into the future. That one-way property is what Tarjan's SCC algorithm relies on.

Back edges are the cycle certificate. A directed graph has a cycle if and only if DFS finds a back edge. A back edge u to v plus the tree path from v to u is a cycle. Conversely, in any cycle, the first vertex DFS discovers reaches every other cycle vertex by a white path, so the cycle edge that returns to it is examined while it is GRAY.

Why undirected graphs have only two

In an undirected graph only tree and back edges exist. Take any edge {u, v} and suppose u is discovered first. While u is GRAY, v is WHITE and reachable through that edge, so v becomes a descendant of u. That edge is then either the tree edge to v, or it is examined from v while u is still GRAY, which makes it a back edge. A forward or cross edge would need an endpoint to finish without examining the edge, and DFS examines every edge at each endpoint.

Two implementation details follow. Each undirected edge is seen twice, once from each side, so classify it the first time and ignore the second. And the edge back to the parent must be skipped by edge identity, not by vertex. If there are two parallel edges between p and u, the second one is a genuine back edge that makes the pair 2-edge-connected. Skipping by "neighbour equals parent" hides it and reports a false bridge.

An iterative classifier that matches recursion

Recursive DFS is the clearest statement, but recursion limits break it on deep graphs. Python's default limit is 1,000 frames, and a path graph with a million vertices will exhaust a native stack too. The iterative version below keeps an explicit stack of (vertex, neighbour iterator) pairs. It resumes each vertex's adjacency list exactly where it stopped, so it visits and timestamps vertices in the same order as the recursive version.

WHITE, GRAY, BLACK = 0, 1, 2

def classify(adj):
    """adj: list of out-neighbour lists for vertices 0..n-1 (directed)."""
    n = len(adj)
    color, disc, fin, parent = [WHITE] * n, [0] * n, [0] * n, [-1] * n
    kinds, t = [], 0
    for root in range(n):
        if color[root] != WHITE:
            continue
        t += 1; disc[root] = t; color[root] = GRAY
        stack = [(root, iter(adj[root]))]
        while stack:
            u, it = stack[-1]
            for v in it:
                if color[v] == WHITE:
                    kinds.append((u, v, "tree"))
                    parent[v] = u
                    t += 1; disc[v] = t; color[v] = GRAY
                    stack.append((v, iter(adj[v])))
                    break                       # descend; resume u's iterator later
                if color[v] == GRAY:
                    kinds.append((u, v, "back"))
                elif disc[u] < disc[v]:
                    kinds.append((u, v, "forward"))
                else:
                    kinds.append((u, v, "cross"))
            else:                               # iterator exhausted: u is finished
                color[u] = BLACK
                t += 1; fin[u] = t
                stack.pop()
    return kinds, disc, fin, parent

The for ... else is doing real work. The else branch runs only when the iterator is exhausted without a break, which is exactly when u has no unexamined edges left. A common wrong version pushes all of u's neighbours onto the stack at once. That visits vertices in a valid order for reachability, but the order is not DFS, and its edge labels and finish times are wrong.

Worked example: six vertices, nine edges

Take vertices a to f with adjacency lists a: [b, d, e], b: [c, d], c: [a], d: [c], e: [d], f: [e], and start at a. The clock runs as follows. a is discovered at 1, b at 2 through a tree edge, and c at 3. c's edge to a finds a GRAY vertex, so it is a back edge, and a, b, c form a cycle. c finishes at 4. Back at b, d is discovered at 5. d's edge to c finds c BLACK with disc 3, earlier than 5, so it is a cross edge. d finishes at 6 and b at 7. Back at a, the edge to d finds d BLACK with disc 5, later than a's 1, so it is a forward edge. e is discovered at 8, and its edge to d is a cross edge. e finishes at 9 and a at 10. The outer loop then restarts at f, discovered at 11. Its edge to e is a cross edge between trees, and f finishes at 12.

Check the parenthesis property: [1,10] contains [2,7], which contains [3,4] and [5,6], and [8,9] sits beside [2,7] inside [1,10]. Check the cross edges: d to c has fin[c] = 4 < disc[d] = 5, e to d has 6 < 8, and f to e has 9 < 11. All three point backward in time, as the theory says they must.

Low-links: from labels to bridges and components

Low-link values make the classification useful. Define low[u] as the smallest discovery time reachable from u's subtree using tree edges downward and then at most one back edge. In an undirected graph, the tree edge from parent p to child u is a bridge exactly when low[u] > disc[p]. If nothing in u's subtree has a back edge reaching p or above, removing the edge disconnects the subtree. The iterative version below skips the parent edge by edge ID, so parallel edges are handled correctly.

def bridges(n, edges):
    """edges: list of (u, v) undirected; returns indices of bridge edges."""
    adj = [[] for _ in range(n)]
    for i, (u, v) in enumerate(edges):
        adj[u].append((v, i))
        adj[v].append((u, i))
    disc, low, t, out = [0] * n, [0] * n, 1, []
    for root in range(n):
        if disc[root]:
            continue
        disc[root] = low[root] = t; t += 1
        stack = [(root, -1, iter(adj[root]))]
        while stack:
            u, pe, it = stack[-1]
            for v, eid in it:
                if eid == pe:
                    continue                    # the tree edge we came in on, by identity
                if disc[v]:
                    low[u] = min(low[u], disc[v])   # back edge (or its second sighting)
                else:
                    disc[v] = low[v] = t; t += 1
                    stack.append((v, eid, iter(adj[v])))
                    break
            else:
                stack.pop()
                if stack:
                    p = stack[-1][0]
                    low[p] = min(low[p], low[u])
                    if low[u] > disc[p]:
                        out.append(pe)
    return out

Articulation points use the same values with >= in place of > for non-root vertices, plus the rule that a root is an articulation point when it has two or more tree children. In directed graphs, Tarjan's SCC algorithm computes low-links over back edges and over cross edges whose target is still on its component stack. A vertex with low[u] == disc[u] is the root of a component. Topological order is the reverse of finishing order, valid exactly when the back-edge list is empty.

Testing a classifier

Because the classification is determined by the intervals and the parent array, you can verify any implementation after the fact. Generate random small graphs, run the classifier, and assert the timestamp relation from the table for every labelled edge. Also compare against a plain recursive reference on graphs small enough for recursion.

import random

def check(adj):
    kinds, disc, fin, parent = classify(adj)
    anc = lambda a, b: disc[a] <= disc[b] and fin[b] <= fin[a]
    for u, v, k in kinds:
        if k == "tree":    assert parent[v] == u
        if k == "back":    assert anc(v, u)
        if k == "forward": assert anc(u, v) and u != v
        if k == "cross":   assert fin[v] < disc[u]
    assert len(kinds) == sum(len(a) for a in adj)    # every edge labelled once

for _ in range(2000):
    n = random.randint(1, 9)
    check([[random.randrange(n) for _ in range(random.randint(0, 3))] for _ in range(n)])

The random adjacency lists include self-loops and duplicate edges on purpose. A self-loop must come out as a back edge, because u is GRAY when its own edge is examined. That makes it a cycle of length one, which matters for deadlock detection in wait-for graphs. A second copy of a tree edge comes out as a forward edge, because by then its target is a finished child, so the checker must not assume that forward edges skip a level.

Failure modes

• Stack overflow. Recursive DFS on a long chain dies on the recursion limit or the native stack. Use the iterator-stack form for anything that comes from user data.
• Push-all-neighbours "DFS". It is correct for reachability and wrong for timestamps, edge types, low-links and topological order. The bugs show up only on graphs with forward or cross edges.
• Parent skip by vertex. In undirected multigraphs it hides parallel edges and reports false bridges.
• Two-colour visited flags. With only visited and unvisited, back edges and cross edges look the same, so directed cycle detection reports cycles in acyclic graphs. GRAY is not optional.
• Forgetting the restart loop. DFS from a single root classifies only one tree. Unreached vertices keep zero timestamps, and the ancestor test then gives nonsense.
• Separate clocks. Using one counter for discovery and another for finish breaks the parenthesis comparisons. Use one shared clock.

Trade-offs

Classification costs O(V + E) time and O(V) extra memory beyond the edge labels, the same as plain DFS. Storing labels for every edge costs O(E). Many uses need only counts or the first back edge, so pass a callback instead of building a list. On very large graphs, DFS's sequential nature is a real limit. It does not parallelise well, so distributed systems often answer the underlying question differently, for example with BFS-based or label-propagation connectivity. Use the DFS tree when the graph fits on one machine and you need what only it gives: cycle certificates, low-links, and constant-time ancestor queries.

Related reading on this site: BFS and DFS side by side, iterative DFS with an explicit stack, directed cycle detection, bridges and articulation points and Tarjan's strongly connected components.

What to do next

1. Implement the iterative classifier above and run the randomized checker until it passes 2,000 graphs.
2. Trace the worked example by hand, then change a's adjacency order to [e, d, b] and predict the new labels before running it.
3. Add the ancestor test and use it to answer "is x inside y's subtree" queries in O(1).
4. Implement bridges with edge-ID parent skipping and test it on a multigraph with parallel edges.
5. Extend the classifier into Tarjan's SCC algorithm by adding an on-stack set and low-link updates.
6. Replace any push-all-neighbours DFS in your codebase that relies on order or finish times.