Strongly Connected Components
Notes
- A strongly connected component of a graph G is the maximal set of vertices, C ⊆ G, such that for every pair of vertexes u,v in C, there is a path from u to v and a path from v to u. Or u is reachable from v and v is reachable from u ($u \rightsquigarrow v , v \rightsquigarrow i$).
- Consider This Graph.
- Consider This graph.
- For a graph, ET is found by reversing the direction of all the edges
- ie if (u,v) ∈ E, (v,u) ∈ ET
- The strongly connected components of E and ET are the same.
- This fact is used in the following algorithm
-
STRONGLY-CONNECTED-COMPONENTS(G)
- Call DFS(G) to compute u.f for each vertex u
- Compute GT
- Call DFS(GT) but select edges by decreasing values of u.f computed in the previous DFS algorithm.
- Output the vertices of each tree in the depth first forest formed in the last DFS search as strongly connected components.
- Do the DFS
- The nodes selected for the DFS were c, g, f, h, d, b, e, a
- Reverse the edges
- Do another DFS, but start with the highest finish time available
- In the end, the results are:
- b,a,e
- f,g
- c,d
- h
- If you think about it, the last finish time will tend to be leaves in the DFS tree
- CLRS proves that G and GT have the same strongly connected components.
- But if you think about it, a starting node in a strongly connected DFS search, will also be the ending node.
- Work through this on this graph.