Topological sort & strongly connected components

Topological sort

A topological sort of a DAG $G$ is a linear order of all vertices such that every edge $(u,v)$ has $u$ before $v$. It exists iff $G$ is a DAG (no directed cycle). The CLRS algorithm is a one-liner on top of DFS:

1. Run DFS to compute finish times $v.f$.
2. As each vertex finishes, push it onto the front of a list.
3. Return the list.

That returns vertices in decreasing finish time. Why it works: for any DAG edge $(u,v)$, DFS gives $v.f<u.f$ (Theorem 20.12) — when $(u,v)$ is explored, $v$ is never gray (that would be a back edge, hence a cycle), so $v$ is white-then-finishes-before-$u$, or already black with a smaller finish. Ordering by decreasing $f$ therefore places $u$ before $v$ for every edge. Running time: $\Theta (V+E)$, same as DFS.

Alternative — Kahn's in-degree method. Repeatedly remove a vertex of in-degree 0 and decrement its neighbours' in-degrees, using a queue. Also $\Theta (V+E)$; if fewer than $|V|$ vertices come out, the graph had a cycle.

Worked example. On the “getting dressed” DAG (undershorts before pants, pants before belt and shoes, shirt before belt and tie, belt and tie before jacket, socks before shoes), DFS-by-finish-time yields a valid dressing order such as watch undershorts socks shirt tie pants shoes belt jacket — every prerequisite precedes what depends on it.

Strongly connected components

An SCC of a directed graph is a maximal set $C$ where every pair $u,v\in C$ is mutually reachable ($u⇝v$ and $v⇝u$). The transpose $G^{\mathsf{T}}$ reverses every edge; $G$ and $G^{\mathsf{T}}$ have the same SCCs. Contracting each SCC to a point gives the component graph, which is always a DAG.

Kosaraju's algorithm (CLRS 20.5) — four steps, $\Theta (V+E)$:

1. Run DFS$(G)$ to compute finish times $u.f$.
2. Compute $G^{\mathsf{T}}$.
3. Run DFS$(G^{\mathsf{T}})$, starting vertices in decreasing $u.f$ order from step 1.
4. Each tree of that second forest is one SCC.

Why it works: the SCC with the largest finish time is a source in the component DAG, so in $G^{\mathsf{T}}$ it is a sink — the second DFS, started there, can reach exactly that SCC and no further (Corollary 20.15 + the white-path theorem). Peeling SCCs in decreasing-finish order isolates one component per tree.