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 Ο(V2) 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 GT, 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)
- call DFS(G) to compute finishing times f[u] for each vertex u
- compute GT
- call DFS(GT), but in the main loop of DFS, consider the vertices in order of decreasing f[u]
- 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.
