Strongly connected component

From Wikipedia, the free encyclopedia

A directed graph is called strongly connected if there is a path from each vertex in the graph to every other vertex. The strongly connected components (SCC) of a directed graph are its maximal strongly connected subgraphs. These form a partition of the graph. If each strongly connected component is contracted to a single vertex, the resulting graph is a directed acyclic 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.

Contents 1 Time execution 2 Algorithm 3 See also 4 References

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

[edit] 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] See also

• Connected component

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