Depth-First Search

Overview

Depth-first search operates on a graph $G=⟨V,E⟩$ and a source vertex $s$.

To keep track of progress, DFS colors each vertex white, gray, or black. All vertices start out white. They are colored gray upon discovery. They are painted black once all edges have been explored.

Vertices also typically have two timestamps recorded: on discovery and on finish.

Depth-First Forests

To color an entire graph black, BFS may need to be invoked multiple times. After each invocation of BFS, a new invocation can be run with any remaining white vertex as the source. Each invocation yields a depth-first tree. Multiple invocations yield a depth-first forest.

Edge Classification

A depth-first forest can contain four different types of edges:

1. A tree edge is an edge $⟨u,v⟩$ such that $v$ was first discovered by exploring edge $⟨u,v⟩$.
2. A back edge is an edge $⟨u,v⟩$ connecting vertex $u$ to an ancestor $v$.
   1. Self-loops are considered back edges.
3. A forward edge is a non-tree edge $⟨u,v⟩$ connecting vertex $u$ to a proper descendant $v$.
4. A cross edge is any other edge.

Parenthesis Theorem

In any depth-first search of a graph, for any two vertices $u$ and $v$, exactly one of the following three conditions holds:

1. The intervals $[u.d,u.f]$ and $[v.d,v.f]$ are disjoint.
   • No ancestor-descendant relation exists between $u$ and $v$.
2. The interval $[u.d,u.f]$ is contained entirely within $[v.d,v.f]$.
   • $u$ is a descendant of $v$.
3. The interval $[v.d,v.f]$ is contained entirely within $[u.d,u.f]$.
   • $v$ is a descendant of $u$.

White-Path Theorem

In a depth-first forest of a directed or undirected graph $G=⟨V,E⟩$, vertex $v$ is a descendant of vertex $u$ if and only if at the time $u.d$ that the search discovers $u$, there is a path from $u$ to $v$ consisting entirely of white vertices.

Topological Sort

A topological sort of a directed acyclic graph $G$ is an ordering of all its vertices such that if $G$ contains an edge $⟨u,v⟩$, then $u$ appears before $v$ in the ordering.

Call depth-first search on $G$ to compute finish times $v.f$ for each vertex $v$. As each vertex is finished, insert it onto the front of a linked list. Return the list when all vertices are processed.

Kosaraju's Algorithm

Let $G$ be a directed graph. Assuming $G$ is represented as an adjacency-list, Kosaraju's algorithm is a $\mathrm{\Theta }(|V|+|E|)$-time procedure for finding the strongly-connected components of $G$.

1. Call $\text{DFS}(G)$ to compute finish times $u.f$ for each vertex $u$.
2. Create $G^T$.
3. Call $\text{DFS}(G^T)$, but in the main loop of DFS, consider the vertices in order of decreasing $u.f$.
4. Output the vertices of each tree in the forest formed in line (3) as a separate strongly connected component.