Strongly Connected Components

Kosaraju · Tarjan

1:00

How to find all maximal mutually-reachable groups in a directed graph using Kosaraju's two-pass and Tarjan's one-pass algorithms.

By the end, you can

Define strongly connected component and explain the partition property.
Determine by inspection which vertices form an SCC in a small directed graph.
Describe the condensation and explain why it is always a DAG.
Explain the purpose of the finish-order stack and the transpose in Kosaraju's algorithm.
Trace Tarjan's discovery index and low-link updates through a DFS, identify SCC roots, and state the pop condition.
Compare Kosaraju and Tarjan on number of passes, need for a transpose, and asymptotic complexity.
Identify at least two real-world problems solved with SCCs.

Up next in Algorithms & Graph Algorithms