Strongly Connected Components

Application of topological sort: decomposing a directed graph into its strongly connected components

This decomposition is important as it is used to divide a single directed graph into pieces for further processing. A strongly connected component of a directed graph G = ( V, E ) is a maximal set of vertices, U Í V such that  " u, v Î U . u is reachable from v and v is reachable from u.

The algorithm for finding these strongly connected components uses the transpose of G, G^T.

G =  ( V, E ),  G^T =  ( V, E^T ), where E^T  =  {  ( u, v ): ( v, u ) Î E }

 G^T is the same as G except all the arrows on the edges are reversed. Note: G and  G^T have the same strongly connected components. If you can get from u to v and from v to u in G, you reverse the paths in  G^T and you can as well.

The strongly connected component algorithm is:

Strongly-Connected-Components ( G )

1. Use DFS ( G ) to compute f[u]  " u Î V
2. Compute  G^T
3. Execute DFS ( G^T ) but instead, in the main DFS loop grab vertices in the order of decreasing f[u] as computed in DFS ( G )
4. Output the vertices if each tree in the depth-first forest of step 3 as a separate strongly connected component.

This algorithm runs in twice the time of DFS ( G ) which is Q ( | V | + | E | )

Can prove that r Î V is in a strongly connected component that consists of al v Î G that v can reach in G^T  (see textbook)