Depth-first search & edge classification

Depth-first vs breadth-first

Where BFS explores a single source level by level with a queue, depth-first search plunges as deep as possible before backtracking, restarts from any remaining white vertex, and so produces a depth-first forest of possibly several trees. DFS runs in $\Theta(V + E)$ by the same aggregate argument as BFS.

DFS's real output is two timestamps per vertex: $u.d$ (discovery, when $u$ is grayed) and $u.f$ (finish, when $u$ is blackened). A global clock ticks before each event, so all $2|V|$ timestamps are distinct integers in $[1, 2|V|]$. The interval $[u.d, u.f]$ is exactly the time $u$ stays gray.

The parenthesis structure

Parenthesis Theorem (20.7). For any two vertices, their intervals $[u.d, u.f]$ and $[v.d, v.f]$ are either disjoint (neither is an ancestor of the other) or nested (one is a descendant of the other). They never partially overlap — exactly like balanced parentheses. Corollary: $v$ is a proper descendant of $u$ iff $u.d < v.d < v.f < u.f$.

Four edge types

Classify an edge $(u, v)$ by the colour of $v$ the first time you explore it:

- Tree edge — $v$ is white: $v$ is discovered via this edge (a child in the DFS tree). - Back edge — $v$ is gray: $v$ is an ancestor of $u$. A self-loop is a back edge. - Forward edge — $v$ is black and $u.d < v.d$: $v$ is a deeper descendant, but not via this edge. - Cross edge — $v$ is black and $u.d > v.d$: $u$ and $v$ are unrelated by ancestry.

In an undirected graph only tree and back edges occur (Theorem 20.10).

Cycle detection — the punchline

A directed graph has a cycle iff a DFS produces a back edge (an edge to a gray vertex). So cycle detection is free: while exploring, if any neighbour is gray, you found a cycle. This single fact drives both topological sort and SCC in the next lesson.

Worked example

On the directed graph $u\to v, u\to x, v\to y, y\to x, x\to v, w\to y, w\to z, z\to z$, a DFS visiting neighbours in sorted order discovers $u, v, y, x, w, z$. The edge $x \to v$ hits gray $v$ (an ancestor of $x$) — a back edge — so the graph has a cycle. The self-loop $z \to z$ is a back edge too.