Strongly connected component

From Free net 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 computes the strongly connected components of a directed graph G=(V,E) using two Depth-first searches (DFSs), one on G, and one on <math>G^T</math>, the transpose graph.

[edit]

Example Algorithm

STRONGLY-CONNECTED COMPONENTS (G)
1 call DFS(G) to compute finishing times f[u] for each vertex u
2 compute <math>G^T</math>
3 call DFS(<math>G^T</math>), 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]