Strongly connected component

Graph with SCC marked

A directed graph is called strongly connected if for every pair of vertices u and v there is a path from u to v and a path from v to u. The strongly connected components (SCC) of a directed graph are its maximal strongly connected subgraphs. These form a partition of the graph.

Kosaraju's algorithm, Tarjan's algorithm and Gabow's algorithm all efficiently compute the strongly connected components of a directed graph, but Tarjan's and Gabow's are favoured in practice since they require only one depth-first search rather than two.

Time execution

A linear-time Θ$(V+E)$ algorithm, if the graph is represented as an adjacency list, as a matrix it is an Ο$(V^{2})$ algorithm, computes the strongly connected components of a directed graph G=(V,E) using two Depth-first searches (DFSs), one on G, and one on $G^{T}$, the transpose graph. Equivalently, Breadth-first search (BFS) can be used instead of DFS.

Kosaraju's algorithm

Strongly-connected components (G)

1. call DFS(G) to compute finishing times f[u] for each vertex u
2. compute G^T
3. call DFS(G^T), but in the main loop of DFS, consider the vertices in order of decreasing f[u]
4. produce as output the vertices of each tree in the DFS forest formed in point 3 as a separate SCC.

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 22.5, pp.552–557.