In a directed graph, a Strongly Connected Component (SCC) is a maximal subgraph where every node is reachable from every other node. Identifying these components is crucial for solving problems related to dependency analysis, social network clusters, and circuit design.
While Kosaraju's algorithm is a popular two-pass approach, Tarjan's Algorithm is the gold standard because it finds all SCCs in a single DFS pass.
The Core Concept: Low-Link Values
Tarjan's algorithm relies on two values for each node during a Depth First Search:
- Discovery Time (
ids): The order in which the node was first visited. - Low-Link Value (
low): The smallest discovery time reachable from the node (including itself) through back-edges in the DFS tree.
If a node's ids equals its low, it is the "root" of an SCC. All nodes currently on the recursion stack that were visited after this root belong to the same SCC.
Tarjan's SCC Implementation in Java
import java.util.*;
public class TarjanSCC {
private int n, id;
private int[] ids, low;
private boolean[] onStack;
private Stack<Integer> stack;
private List<List<Integer>> adj;
private List<List<Integer>> sccs;
public List<List<Integer>> findSCCs(int n, List<List<Integer>> adj) {
this.n = n;
this.adj = adj;
this.ids = new int[n];
this.low = new int[n];
this.onStack = new boolean[n];
this.stack = new Stack<>();
this.sccs = new ArrayList<>();
Arrays.fill(ids, -1);
for (int i = 0; i < n; i++) {
if (ids[i] == -1) dfs(i);
}
return sccs;
}
private void dfs(int at) {
stack.push(at);
onStack[at] = true;
ids[at] = low[at] = id++;
for (int to : adj.get(at)) {
if (ids[to] == -1) {
dfs(to);
low[at] = Math.min(low[at], low[to]);
} else if (onStack[to]) {
low[at] = Math.min(low[at], ids[to]);
}
}
// If we found the root of an SCC
if (ids[at] == low[at]) {
List<Integer> scc = new ArrayList<>();
while (!stack.isEmpty()) {
int node = stack.pop();
onStack[node] = false;
low[node] = ids[at];
scc.add(node);
if (node == at) break;
}
sccs.add(scc);
}
}
}
Tarjan's vs. Kosaraju's
| Feature | Tarjan's Algorithm | Kosaraju's Algorithm |
|---|---|---|
| Passes | Single DFS Pass | Two DFS Passes |
| Complexity | $O(V + E)$ | $O(V + E)$ |
| Space | $O(V)$ (Stack + Arrays) | $O(V)$ (Stack + Transposed Graph) |
| Ease of Use | Slightly more complex logic | Easier to understand conceptually |
Real-World Applications
- Deadlock Detection: In operating systems, SCCs in a wait-for graph indicate potential deadlocks.
- Web Crawling: Identifying clusters of highly interlinked pages.
- Software Engineering: Detecting circular dependencies between modules or classes.
Summary
Tarjan's algorithm is a masterpiece of graph theory. By cleverly using discovery times and low-link values, it extracts deep structural information about a graph's connectivity in linear time. Mastering this algorithm is a strong signal of advanced algorithmic thinking, especially in interviews for senior engineering roles.
