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.