Strongly Connected Components
Definition (StronglyConnectedComponents) A strongly connected component of a directed graph G=(V,E) is a maximal set of vertices C⊆V such that ∀u,v∈C, we have both u--->v and v--->u. (---> signifies a path)
Algorithm (FindingStronglyConnectedComponents) Strongly-Connected-Components(G)
- call DFS(G) to compute finishing times f[u] for each vertex u
- compute G^{T}
- call DFS(G^{T}), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1)
- output the vertices of each tree in the depth-first forest formed in line 3 as separte strongly connected components.
attachment:SCC.jpg