Strongly connected component

From Wikipedia, the free encyclopedia

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 efficiently computes the strongly connected components of a directed graph.

[edit] Time execution

A linear-time Θ(V + E) algorithm, if the graph is represented as an adjacency list, as a matrix it is an Ο(V²) 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.

A transpose graph is a graph with all of the edges reversed. It is named because its adjacency matrix is the transpose of the adjacency matrix of the original graph.

[edit] 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.

[edit] 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.