Topological Sort and Strong Connectivity

Many problems are really questions about order. To compile a program you must build each module before the ones that depend on it; to follow a recipe you must chop before you sauté; to finish a degree you must clear the prerequisites of each course. Each of these is a directed acyclic graph, a digraph with no directed cycles, and the task of find a consistent order is topological sorting. Depth-first search, with its finish-time timestamps from the previous lesson, solves it almost incidentally.

Directed acyclic graphs

The absence of cycles is exactly what makes a consistent ordering possible: if task $a$ must precede $b$ and $b$ must precede $a$, no linear order can satisfy both. Here is a small DAG of course prerequisites, where an edge $u\to v$ means $u$ must come before $v$:

Topological order

Picture all the vertices pinned along a horizontal line so that every edge points rightward. The DAG above admits the order $a,b,d,e,c$, and you can check that each of its six edges goes left to right:

Topological orders are usually not unique; $a,d,b,e,c$ works equally well. Two facts tie ordering to acyclicity:

The forward direction is immediate: a directed cycle could never be laid out with all edges pointing the same way. The converse, that every DAG has such an order, is what the algorithm below constructs.

Topological sort via DFS finish times

The key observation, drawn out by all three texts, links acyclicity to depth-first search's edge classification from the previous lesson:¹

A back edge $(u,v)$ runs from $u$ to a gray ancestor $v$; the tree path from $v$ down to $u$ together with that edge forms a cycle. Conversely, in any cycle the first vertex discovered becomes a gray ancestor of the others, so the edge closing the cycle is a back edge. Since DAGs have no back edges, every edge of a DAG is a tree, forward, or cross edge, and for all three of those, the finish times obey $u.f>v.f$. That single inequality is the whole trick:

So we run DFS, and as each vertex finishes we push it onto the front of a list. When DFS completes, the list reads off a valid topological order.²

Correctness. Consider any edge $(u,v)$. When DFS explores it, $v$ is white, gray, or black. It cannot be gray — that would be a back edge, impossible in a DAG. If $v$ is white, it becomes a descendant of $u$ and finishes first, so $u.f>v.f$. If $v$ is black, it already finished, so again $u.f>v.f$. In every case $u$ finishes after $v$, so prepending on finish places $u$ before $v$ in $L$, the defining property of a topological order.

Running time. This is just DFS plus $O(1)$ work per vertex to splice it into the list, so it runs in $\Theta (V+E)$, which is linear.

Concretely, run DFS on the prerequisite DAG from $a$ (ties alphabetical) and read off each vertex's finish time $f$. Sorting the vertices by decreasing $f$ drops them straight into a valid topological order — and every edge, drawn below the sorted line, points rightward:

Why a topological order matters: the evaluation DAG

A problem that looks unrelated brings topological order to life: computing Fibonacci numbers $F_n=F_{n-1}+F_{n-2}$. The naive recursion $\text{Fibo}(n)$ branches into $\text{Fibo}(n-1)$ and $\text{Fibo}(n-2)$, and its call tree is exponential, but most of its nodes are duplicates. If we collapse the identical subproblems into single nodes, the recursion tree becomes a small DAG: one node per value $F_i$, with an edge $F_i\to F_j$ whenever computing $F_i$ needs $F_j$.

To compute $F_n$ we must evaluate every node after the nodes it points to are already known, that is, in a valid topological order of the evaluation DAG. Here the order is read off by level: $F_0,F_1,F_2,\dots ,F_n$. Filling an array in that order computes each value with $O(1)$ work, turning exponential recursion into a single linear sweep:

The lesson generalizes: whenever quantities depend on one another acyclically, their dependency digraph is a DAG, and a topological order is exactly a safe order in which to evaluate them, predecessors first. This is the structural backbone of dynamic programming, which we return to later.

Running Kahn's algorithm on the prerequisite DAG, $a$ is the only source. Emit it, and removing its edges drops $b$ and $d$ to in-degree $0$; emitting $b$ then $d$ frees $e$, and finally $c$. The result is the same order $a,b,d,e,c$ that DFS finish times produced:

Strong connectivity

DAGs are the cycle-free case. What can we say about a general digraph, cycles and all? The right notion of connected for directed graphs is mutual reachability.

Strong connectivity partitions $V$ into SCCs. Collapsing each component to a single super-vertex yields the component graph (or condensation), and a beautiful fact holds:

If it had a cycle, the components on that cycle could all reach one another and would have been merged into one larger component, contradicting maximality. So every directed graph is, at the coarse level of its components, a DAG. SCCs are the standard first step in analyzing a digraph: find the components, contract them, and reason about the resulting DAG.

Here $\left\{a,b\right\}$ form one SCC (each reaches the other) and $\left\{c,d\right\}$ another, and the only edges between the two groups run from $\left\{a,b\right\}$ to $\left\{c,d\right\}$. Collapsing each component to a super-vertex leaves the two-node condensation, itself a DAG, with its own trivial topological order $\left\{a,b\right\}$ then $\left\{c,d\right\}$:

Kosaraju's two-pass algorithm

The cleanest way to find SCCs, due to Kosaraju and Sharir, is two depth-first searches with a transpose in between.³ The transpose $G^{\mathsf{T}}$ is $G$ with every edge reversed; crucially, it has exactly the same SCCs as $G$, because reversing all edges does not affect mutual reachability.

Why it works (the intuition). Imagine the component graph laid out in topological order, sources on the left. The first DFS on $G$ assigns the largest finish time to a vertex in a source component of that DAG. When we then run DFS on $G^{\mathsf{T}}$, where every component-graph edge is reversed, and start from that highest-finishing vertex, we are launching from a sink of the reversed component graph. From a sink, the search cannot leak into any other component, so it visits exactly one SCC and stops. Peeling components off in decreasing finish order keeps this true at every step. The whole procedure is two DFS passes plus a transpose, all linear, so SCCs cost $\Theta (V+E)$.

The picture below makes the source/sink reversal concrete. The first DFS on a graph with three SCCs lands the largest finish time ($12$) inside the source component $\left\{a,b\right\}$; reversing the edges turns that source into a sink, so the second DFS, launched from $a$, is trapped inside one SCC and peels it off cleanly:

Takeaways

• A DAG is a directed graph with no cycle; it has a topological order (every edge points forward) if and only if it is acyclic.
• DFS detects acyclicity by the absence of back edges, and listing vertices in decreasing finish time yields a topological order in $\Theta (V+E)$.
• A topological order is exactly a safe evaluation order for acyclically dependent quantities, predecessors first. Collapsing the Fibonacci recursion into its evaluation DAG and sweeping it in topological order turns exponential recursion into a linear pass, the seed of dynamic programming.
• Strongly connected components are maximal mutually-reachable vertex sets; contracting them always produces a DAG.
• Kosaraju's two-pass DFS (run DFS, transpose, run DFS in decreasing finish order) finds all SCCs in $\Theta (V+E)$; Tarjan's low-link method does it in one pass.