Graph Traversals, Topological Sort & Strongly Connected Components

During Depth-First Search (DFS), each vertex u is assigned two timestamps:

- d[u]: Discovery time (when vertex turns from WHITE to GRAY).

- f[u]: Finish time (when all outgoing edges are explored and vertex turns BLACK).

The Parenthesis Structure:

For any pair u, v, exactly one holds:

1. [d[u], f[u]] and [d[v], f[v]] are entirely disjoint: neither is an ancestor of the other.

2. [d[u], f[u]] is completely contained within [d[v], f[v]]: u is a descendant of v in the DFS forest.

Edge Classification on Directed Graphs:

- Tree Edge: Leads to an unvisited (white) vertex.

- Back Edge: Leads to an ancestor currently on the recursion stack (gray vertex: d[v] < d[u] < f[u] < f[v]). A back edge proves existence of a directed cycle.

- Forward Edge: Leads to a descendant already explored (black vertex: d[u] < d[v] < f[v] < f[u]).

- Cross Edge: Leads to a vertex in another branch/tree (black vertex: d[v] < f[v] < d[u] < f[u]).

A Topological Sort of a directed acyclic graph (DAG) G = (V, E) is a linear ordering of all vertices such that for every directed edge (u, v), vertex u comes before v.

Two Classic Algorithms:

1. DFS Finish Time Ordering: Run DFS on G. As each vertex finishes (f[u]), prepend it to a linked list. The resulting list is a valid topological sort. Time O(V + E).

2. Kahn's In-Degree Algorithm: Compute in-degrees of all vertices. Enqueue all vertices with in-degree 0. Repeatedly dequeue vertex u, add to sorted order, and decrement in-degrees of its neighbors. If a neighbor reaches in-degree 0, enqueue it. Time O(V + E).

Strongly Connected Components (Kosaraju's Algorithm):

A directed graph is strongly connected if every vertex is reachable from every other vertex.

Kosaraju's 2-pass algorithm:

1. Run DFS on G and record vertices in a stack ordered by finish time.

2. Construct the transpose graph G^T (reverse all edge directions).

3. Pop vertices from stack and run DFS on G^T. Each DFS tree corresponds to an SCC.