Discovery and Finish Times: What DFS Edge Classification Encodes

Depth-first search explores a graph by following one edge as far as it goes before retreating. The recursive formulation is four lines. What makes it more than a traversal is the bookkeeping it can carry: a discovery timestamp when a vertex is first entered, a finish timestamp when its last outgoing edge has been examined, and a colour that records whether the vertex is untouched, on the current path, or complete. Those three pieces of state turn the traversal into a classifier of edges, and the classification answers questions about cycles, precedence, and reachability that have nothing to do with the order of visiting.

Two counters and three colours

Each vertex carries a colour and two integer timestamps. White means undiscovered, grey means discovered but not finished, black means finished. A single counter t increments on every timestamp event, so each vertex receives a distinct integer in 1..2n: d[v] on entry, f[v] on exit.

WHITE, GREY, BLACK = 0, 1, 2

def dfs(adj):
    n = len(adj)
    color = [WHITE] * n
    d = [0] * n
    f = [0] * n
    t = 0
    parent = [-1] * n

    def visit(u):
        nonlocal t
        color[u] = GREY
        t += 1
        d[u] = t
        for v in adj[u]:
            if color[v] == WHITE:
                parent[v] = u
                visit(v)
        color[u] = BLACK
        t += 1
        f[u] = t

    for u in range(n):
        if color[u] == WHITE:
            visit(u)
    return d, f, parent

The outer loop matters as much as the recursion. A single call from one source reaches only the source’s out-component; iterating over all vertices in index order produces a depth-first forest covering the whole graph, and the number of trees in that forest is the number of times the outer loop found a white vertex. That number depends on the vertex ordering: it is at least the number of source components of the condensation, and it equals that number exactly when every vertex outside a source component is reachable from an earlier-indexed one. Strongly connected component algorithms rely on the forest for its interval structure rather than for its tree count.

The bracket structure of intervals

The interval [d[v], f[v]] behaves like a properly nested set of brackets. For any two vertices u and v, exactly one of three relations holds:

• the intervals are disjoint, and whichever finished first finished entirely before the other was discovered;
• one interval is contained in the other, and the contained vertex is a descendant of the containing one in the forest;
• they are identical, which happens only for the same vertex.

The nesting follows from the recursion. A vertex stays grey for the whole time its subtree is explored, so every vertex discovered in that window is discovered and finished inside the window. There is no fourth case where intervals overlap partially, because the traversal is depth-first: it cannot start a second branch before finishing the first.

That nesting is what makes the timestamps more than a log. Given only d and f for every vertex, ancestor relationships in the forest can be tested in constant time: u is an ancestor of v exactly when d[u] < d[v] and f[v] < f[u]. No tree walk is needed, which is why the arrays are worth 2n integers of memory in algorithms that query ancestry repeatedly.

Four classes of directed edge

With timestamps in hand, each edge (u, v) examined during the traversal falls into one of four classes, distinguished by v’s colour at the moment the edge is inspected.

Tree edges lead to a white vertex. They are the edges of the forest, and there are exactly n − c of them when the forest has c trees.

Back edges lead to a grey vertex: an ancestor on the current path. A back edge is a cycle, and a directed graph is acyclic exactly when its depth-first search produces no back edges. This is the standard linear-time cycle test, and it is exact — unlike the undirected case, where an edge to an already-visited vertex may be nothing more than the parent edge traversed backwards.

Forward edges lead to a black vertex that is a descendant in the forest, so d[u] < d[v] and f[v] < f[u]. They are shortcuts over paths the traversal already explored.

Cross edges lead to a black vertex that is neither ancestor nor descendant: disjoint intervals, with f[v] < d[u]. They jump between finished subtrees, and in a directed graph they can point in either direction relative to vertex numbering.

A recursive DFS with colour testing classifies each edge in O(1), so the whole classification costs O(n + m). The colour test is essential; comparing timestamps after the fact cannot distinguish a forward edge from a cross edge without also checking the forest structure, and comparing only timestamps cannot see back edges to vertices that were grey at inspection time but are black by the time the algorithm ends.

Why undirected graphs have only two classes

In an undirected graph, every edge is traversed twice, once from each endpoint, if the representation stores both directions. The second traversal sees a black or grey vertex and would appear to be a cross or forward edge. It is neither. In an undirected depth-first search, every edge is either a tree edge or a back edge, and the reason is structural.

Suppose (u, v) is examined from u and v is already black. Then v was discovered before the edge was examined and finished before u finished, so f[v] < f[u]. But v was discovered while u was grey or before u was discovered at all. If v was discovered before u, the edge would have been examined from v while u was white, making it a tree edge from v. If v was discovered while u was grey, then v is a descendant of u and the edge is a back edge. Neither case leaves room for a forward or cross edge. Implementations must therefore skip the edge back to the parent (or count it as the same edge) or they will report a spurious cycle in a tree.

The distinction has a practical consequence. Cycle detection on an undirected graph cannot use “edge to a visited vertex” as the test; it must use “edge to a grey vertex that is not the parent”, or it must count edges and vertices and compare against the component size. The counting test is a useful cross-check: a connected component with k vertices is acyclic exactly when it has k − 1 edges.

Where the classification is used directly

Topological sorting of a directed acyclic graph is a depth-first search whose output is the reverse of the finish order. The correctness argument is exactly the edge classification: if (u, v) is an edge, then v cannot finish before u unless the edge is a back edge, and a back edge would mean a cycle. The full argument appears in the finish-order derivation.

Strongly connected components use the same timestamps differently. Tarjan’s algorithm replaces the finish order with a stack and a lowlink value, but the underlying fact — that a component is closed under back edges and separated by tree edges — is the same interval structure read from the other end.

Path enumeration and backtracking use the grey/black distinction as their central data structure. A vertex is on the current path exactly when it is grey, so the recursion can emit a path when it reaches a target and unmark on the way out. The explicit-stack formulation exists mainly because this recursion depth is unbounded.

The recursion limit is part of the specification

A recursive depth-first search uses stack frames proportional to the longest simple path, which can be n. On a graph of a million vertices forming a chain, the recursion goes a million frames deep, and a typical thread stack of 8 MB is exhausted well before that. Languages without tail calls cannot optimize this away, and the resulting crash is a stack overflow rather than a wrong answer, which makes it easy to diagnose but impossible to recover from inside the traversal.

The iterative formulation is not merely a portability workaround. It changes which operations are cheap: pausing and resuming a traversal, serializing its state, and running several searches interleaved all become straightforward when the stack is a data structure the caller owns. The cost is that the iterative version must reproduce the finish-time bookkeeping explicitly, and getting the “resume after this child” state right is where most iterative implementations diverge from the recursive semantics.