Tarjan's Strongly Connected Components
Algorithm to find all strongly connected components (SCCs) in a directed graph in linear time. A strongly connected component is a maximal set of vertices where every vertex is reachable from every other vertex. Invented by Robert Tarjan in 1972, it uses a single DFS pass with low-link values to identify SCCs.
Visualization
Interactive visualization for Tarjan's Strongly Connected Components
Tarjan's SCC Algorithm
• Time: O(V + E)
• Single DFS pass
• Finds all strongly connected components
Interactive visualization with step-by-step execution
Implementation
1class TarjanSCC {
2 private index = 0;
3 private stack: number[] = [];
4 private indices: Map<number, number> = new Map();
5 private lowLinks: Map<number, number> = new Map();
6 private onStack: Set<number> = new Set();
7 private sccs: number[][] = [];
8
9 findSCCs(graph: Map<number, number[]>): number[][] {
10 for (const vertex of graph.keys()) {
11 if (!this.indices.has(vertex)) {
12 this.strongConnect(vertex, graph);
13 }
14 }
15 return this.sccs;
16 }
17
18 private strongConnect(v: number, graph: Map<number, number[]>): void {
19 this.indices.set(v, this.index);
20 this.lowLinks.set(v, this.index);
21 this.index++;
22 this.stack.push(v);
23 this.onStack.add(v);
24
25 const neighbors = graph.get(v) || [];
26 for (const w of neighbors) {
27 if (!this.indices.has(w)) {
28 this.strongConnect(w, graph);
29 this.lowLinks.set(v, Math.min(this.lowLinks.get(v)!, this.lowLinks.get(w)!));
30 } else if (this.onStack.has(w)) {
31 this.lowLinks.set(v, Math.min(this.lowLinks.get(v)!, this.indices.get(w)!));
32 }
33 }
34
35 if (this.lowLinks.get(v) === this.indices.get(v)) {
36 const scc: number[] = [];
37 let w: number;
38 do {
39 w = this.stack.pop()!;
40 this.onStack.delete(w);
41 scc.push(w);
42 } while (w !== v);
43 this.sccs.push(scc);
44 }
45 }
46}Deep Dive
Theoretical Foundation
Tarjan's algorithm maintains a stack of vertices and assigns each vertex an index (discovery time) and low-link value (smallest index reachable). When a vertex's low-link equals its index, it's an SCC root. All vertices on stack above it form one SCC. The algorithm combines DFS with stack to detect back edges efficiently.
Complexity
Time
O(V + E)
O(V + E)
O(V + E)
Space
O(V)
Applications
Industry Use
Compiler optimization (call graph analysis)
Social network analysis (mutually connected groups)
Web page ranking and link analysis
Deadlock detection in database systems
Module dependency analysis in software
Circuit design verification and optimization
Game theory (finding stable coalitions)
Use Cases
Related Algorithms
Depth-First Search (DFS)
Graph traversal exploring as deep as possible before backtracking. DFS is a fundamental algorithm that uses a stack (either implicitly through recursion or explicitly) to explore graph vertices. It's essential for cycle detection, topological sorting, and pathfinding problems.
Breadth-First Search (BFS)
Level-by-level graph traversal guaranteeing shortest paths in unweighted graphs. BFS uses a queue to explore vertices level by level, making it optimal for finding shortest paths and solving problems that require exploring nearest neighbors first.
Dijkstra's Algorithm
Finds shortest path from source to all vertices in weighted graph with non-negative edges. Uses greedy approach with priority queue.
Floyd-Warshall Algorithm
Floyd-Warshall is an all-pairs shortest path algorithm that finds shortest distances between every pair of vertices in a weighted graph. Unlike Dijkstra (single-source), it computes shortest paths from all vertices to all other vertices simultaneously. The algorithm can handle negative edge weights but not negative cycles. Developed independently by Robert Floyd, Bernard Roy, and Stephen Warshall in the early 1960s.