Strongly connected components (SCCs), Tarjan's and Kosaraju's algorithms, DAGs and topological sorting, the correspondence with partial orders, and dynamic programming on DAGs.
In a directed graph G=(V,A), vertex v is reachable from vertex u if there exists a directed path from u to v. We write u⇝v.
Definition 2 (Strongly connected).
Two vertices u and v of a directed graph G are mutually reachable if u⇝v and v⇝u. The graph G is strongly connected if every pair of vertices is mutually reachable.
Theorem 3 (Mutual reachability is an equivalence relation).
The relation "mutually reachable" on V is an equivalence relation.
Proof.
Reflexivity: u⇝u via the path of length 0. Symmetry: immediate from the definition. Transitivity: if u⇝v and v⇝w, concatenation of paths gives u⇝w; the reverse direction is analogous.□
2 Strongly Connected Components and the SCC Condensation
Definition 4 (Strongly connected component).
The equivalence classes of mutual reachability are called the strongly connected components (SCCs) of G.
Theorem 5 (The SCC condensation is a DAG).
The graph GSCC obtained by contracting each SCC to a single vertex is a DAG (directed acyclic graph).
Proof.
Suppose GSCC contains a directed cycle C1→C2→⋯→Ck→C1. For any vertex u∈Ci and any vertex v∈Cj, a directed path from u to v can be constructed by traversing from Ci to Cj through the cycle (using paths within each SCC to move between boundary vertices). Similarly, a path from v to u exists. Thus u and v are mutually reachable and belong to the same SCC, contradicting Ci=Cj.□
3 Depth-First Search (DFS)
Depth-first search is an indispensable tool for analyzing the structure of directed graphs.
Algorithm 1: Depth-First Search (DFS)
Input:
Directed graph G=(V,A)
Output:
Discovery times disc[v] and finish times fin[v]
for allv∈V
visited[v]←false
end for
time←0
for allv∈V
if¬visited[v]
DFS-Visit(G,v)
end if
end for
procedure DFS-Visit G,u
visited[u]←true
time←time+1
disc[u]←time
for all(u,v)∈A
if¬visited[v]
DFS-Visit(G,v)
end if
end for
time←time+1
fin[u]←time
end procedure
DFS runs in O(∣V∣+∣A∣) time. The vertices listed in decreasing order of finish time yield a topological sort.
4 Kosaraju's Algorithm
Kosaraju's algorithm uses the reverse graph GR (obtained by reversing every arc) to compute all SCCs in O(∣V∣+∣A∣) time.
Run DFS on G and list the vertices in decreasing order of finish time.
Run DFS on GR, processing vertices in the order obtained in step 1. Each DFS tree in this second pass corresponds to one SCC.
Theorem 6 (Correctness of Kosaraju's algorithm).
The vertex sets produced by the above algorithm are exactly the strongly connected components of G.
Proof.
The vertex with the largest finish time in step 1 belongs to a source SCC (one with in-degree 0) of the condensation DAG. In step 2, DFS on GR from this vertex explores only the vertices within that SCC, because in GR the directions of the condensation are reversed, blocking passage to other SCCs. Proceeding inductively in reverse topological order of the condensation, each SCC is correctly identified.□
5 Tarjan's Algorithm
Tarjan's algorithm computes all SCCs with a single DFS pass. For each vertex v, it maintains the DFS discovery time disc[v] and a value low[v]— the smallest discovery time reachable from v's DFS subtree via back edges. A vertex v with disc[v]=low[v] is the root of an SCC; at that point, the vertices on the stack above v (inclusive) form one SCC.
Remark 7.
Tarjan's algorithm also runs in O(∣V∣+∣A∣) time. Since it avoids constructing the reverse graph, it can be slightly faster in practice than Kosaraju's algorithm.
6 Topological Sorting
Definition 8 (Topological sort).
A topological sort of a DAG G=(V,A) is a total ordering v1,v2,…,vn of V such that i<j whenever (vi,vj)∈A.
Theorem 9 (Existence of a topological sort).
A directed graph G admits a topological sort if and only if G is a DAG.
Proof.
(⇒): If G contained a directed cycle vi1→vi2→⋯→vik→vi1, the ordering would require i1<i2<⋯<ik<i1, a contradiction.(⇐): Every DAG has a vertex of in-degree 0 (if every vertex had positive in-degree, following incoming arcs from any starting vertex would eventually revisit a vertex, producing a directed cycle). Place such a vertex first, remove it, and apply induction to the remaining graph (still a DAG).□
Remark 10.
Listing vertices in decreasing order of DFS finish time yields a topological sort in O(∣V∣+∣A∣) time. Alternatively, Kahn's algorithm — a BFS-based method that repeatedly processes vertices of in-degree 0— achieves the same running time.
7 Connection to Partial Orders
Remark 11.
A DAG can be viewed as the Hasse diagram of a partially ordered set. The reachability relation on a DAG is reflexive, antisymmetric, and transitive, satisfying the axioms of a partial order. A topological sort is a linear extension— a total order consistent with the given partial order. The existence of a linear extension is guaranteed by Szpilrajn's theorem.
8 Dynamic Programming on DAGs
Processing vertices in topological order enables dynamic programming solutions to many optimization problems on DAGs.
Example 12 (Longest path in a DAG).
Let ℓ[v] denote the length of a longest path from s to v. Processing vertices in topological order and computing
ℓ[v]=(u,v)∈Amax(ℓ[u]+w(u,v))
yields the answer in O(∣V∣+∣A∣) time. This works correctly even with negative weights, since there are no cycles.
Example 13 (Counting paths in a DAG).
The number c[v] of distinct paths from s to each vertex v can likewise be computed in topological order:
c[v]=(u,v)∈A∑c[u],
with the initial condition c[s]=1 (and c[v]=0 for vertices not reachable from s).
Remark 14.
By combining SCC decomposition with DP on the condensation DAG, problems on general directed graphs can often be split into two independent tasks: handling the structure within each SCC, and propagating information across SCCs in topological order. This is a fundamental paradigm in the design of algorithms on directed graphs.