Tarjan's Strongly Connected Components Algorithm
Tarjan's strongly connected components algorithm is a single-pass depth-first search procedure that partitions the vertices of a directed graph into maximal strongly connected components in linear O(|V| + |E|) time.
Tarjan's strongly connected components algorithm is a linear-time graph decomposition algorithm within computation and algorithms that partitions the vertex set V of a directed graph G = (V, E) into its maximal strongly connected components (SCCs). Published by American computer scientist Robert E. Tarjan in the SIAM Journal on Computing in 1972—in the paper that established depth-first search (DFS) as a unifying framework for linear-time graph algorithms—the method executes a single depth-first traversal while maintaining an auxiliary stack of active vertices and two integer indices per vertex: a discovery timestamp (index) and a low-link value (lowlink).
Running in optimal O(|V| + |E|) time and O(|V|) space within computational complexity theory, Tarjan's algorithm outputs the strongly connected components of G in reverse topological order of the condensation directed acyclic graph (DAG), simultaneously performing component decomposition and topological sorting in one pass without constructing the transpose graph G⊤ required by Kosaraju's two-pass algorithm. Across formal verification, compiler design, and systems biology, Tarjan's algorithm underpins 2-SAT boolean satisfiability solvers, Static Single Assignment (SSA) loop detection, Markov chain ergodic state classification, project-closure network reductions for the Ford–Fulkerson algorithm, and autocatalytic cycle identification in metabolic reaction networks.
Mathematical Foundations: Mutual Reachability and the Condensation DAG
Strongly Connected Equivalence Classes
Let G = (V, E) be a directed graph. Two vertices u, v ∈ V are strongly connected (u ∼ v) if G contains directed paths from u to v and from v to u. Because ∼ is reflexive, symmetric, and transitive, it partitions V into disjoint equivalence classes C1, C2, ..., Ck called the strongly connected components of G (complementing undirected components maintained via a disjoint-set data structure).
Condensation Graph Acyclicity and DFS Subtree Property
Contracting each component Ci into a super-vertex ci yields the condensation graph GSCC = (VSCC, ESCC), which is always a directed acyclic graph (DAG) by component maximality. Tarjan (1972) proved that every strongly connected component Ci induces a connected subtree of any DFS forest F of G, with the first vertex ri ∈ Ci visited during DFS serving as the unique component root (highest ancestor in F).
The Low-Link Invariant and Single-Pass Stack Mechanics
DFS Discovery Index, Low-Link Recurrence, and Active Stack Invariant
During DFS on G, each edge (u, v) ∈ E is a tree edge, back edge, forward edge, or cross edge. Tarjan's algorithm maintains a counter t ∈ {0, ..., |V| − 1}, an active component stack S, and a flag *onStack*[v]. When u is first visited, it is pushed onto S (*onStack*[u] ← true) and assigned *index*[u] ← *lowlink*[u] ← t (with t ← t + 1), where *lowlink*[u] tracks the smallest index reachable from u's DFS subtree via at most one back or in-component cross edge. For each outgoing edge (u, v) ∈ E:
- Unvisited Neighbor (*index*[v] undefined — Tree Edge): Recursively call DFS(v) and set *lowlink*[u] ← min(*lowlink*[u], *lowlink*[v]).
- Visited Neighbor on Stack S (*onStack*[v] = true): Set *lowlink*[u] ← min(*lowlink*[u], *index*[v]).
- Visited Neighbor Already Popped (*onStack*[v] = false): Ignore (u, v) because v's SCC is already closed and cannot reach u.
Component Root Detection and Stack Popping
After exploring all outgoing edges of u, u is the root of an SCC if and only if:
Because all earlier-completed child SCCs below u have already been popped, the vertices of u's SCC sit contiguously at the top of S down to u. Popping vertices w from S (*onStack*[w] ← false) until w = u emits the component in reverse topological order of GSCC.
| SCC Algorithm | Traversal Strategy | Auxiliary Data Structures | Graph Passes | Worst-Case Time & Space |
|---|---|---|---|---|
| Tarjan's Algorithm (1972) | Single DFS with lowlink | 1 stack S, *index*[], *lowlink*[], *onStack*[] | 1 DFS pass on G | O(|V| + |E|) time, O(|V|) space |
| Kosaraju–Sharir Algorithm (1978/1981) | Postorder DFS on G, then DFS on G⊤ | Finishing-time stack + transpose graph G⊤ | 2 DFS passes (G and G⊤) | O(|V| + |E|) time, O(|V| + |E|) for G⊤ |
| Cheriyan–Mehlhorn / Gabow Path-Based (1996/2000) | Single DFS with two stacks (S and boundary P) | Vertex stack S + root-candidate stack P | 1 DFS pass on G | O(|V| + |E|) time, avoids lowlink arithmetic |
| Forward–Backward Parallel (Fleischer et al. 2000) | Divide-and-conquer BFS reachability | Parallel forward/backward queues | O(log |V|) average | O(|V|·|E|) worst-case; parallel GPU friendly |
Related Decomposition Variants and Scientific Applications
Biconnected Components, 2-SAT Solvers, and Metabolic Networks
In the same 1972 paper, Tarjan adapted the lowlink invariant to undirected graphs to identify articulation points (cut vertices), bridges (cut edges), and biconnected components in linear O(|V| + |E|) time: a non-root vertex u is an articulation point if and only if it has a child v with *lowlink*[v] ≥ *index*[u], and a tree edge (u, v) is a bridge if and only if *lowlink*[v] > *index*[u].
In theoretical computer science, Aspvall, Plass, and Tarjan (1979) used Tarjan's SCC algorithm to solve 2-satisfiability (2-SAT) in linear O(n + m) time: each clause (x ∨ y) is encoded as the implication edges (¬x → y) and (¬y → x), and the formula is satisfiable if and only if no variable xi resides in the same strongly connected component as ¬xi. In systems biology and genome informatics, Tarjan's algorithm partitions metabolic reaction networks into cyclic cores versus acyclic feed-forward hierarchies, and identifies tangled repeat components in assembly de Bruijn graphs.
Frequently Asked Questions
Why does Tarjan's algorithm ignore cross edges to already visited vertices that are no longer on the stack S?
If a vertex v has already been visited (*index*[v] is defined) but is no longer on the active stack S (*onStack*[v] = false), then v's strongly connected component was already explored and popped earlier in the DFS. Consequently, no directed path can exist from v back to the active vertex u (otherwise u would have been reached from v before v's DFS call returned).
Why is Tarjan's algorithm faster in practice than Kosaraju's algorithm?
Although both algorithms run in O(|V| + |E|) asymptotic time, Kosaraju's algorithm performs two complete DFS traversals and requires materializing or traversing the reversed edge set G⊤, doubling memory traffic on large graphs. Tarjan's algorithm traverses each adjacency list once in forward direction and never constructs G⊤.
References
- Tarjan, R. (1972). "Depth-first search and linear graph algorithms." SIAM Journal on Computing, 1(2), 146–160. https://doi.org/10.1137/0201010
- Aspvall, B., Plass, M. F., & Tarjan, R. E. (1979). "A linear-time algorithm for testing the truth of certain quantified boolean formulas." Information Processing Letters, 8(3), 121–123. https://doi.org/10.1016/0020-0190(79)90002-490002-4)
- Sharir, M. (1981). "A strong-connectivity algorithm and its applications in data flow analysis." Computers & Mathematics with Applications, 7(1), 67–72. https://doi.org/10.1016/0898-1221(81)90008-090008-0)
- Gabow, H. N. (2000). "Path-based depth-first search for strong and biconnected components." Information Processing Letters, 74(3–4), 107–114. https://doi.org/10.1016/S0020-0190(00)00051-X00051-X)
- Pearce, D. J. (2016). "A space-efficient algorithm for finding strongly connected components." Information Processing Letters, 116(1), 47–52. https://doi.org/10.1016/j.ipl.2015.08.010