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)

  1. call DFS(G) to compute finishing times f[u] for each vertex u
  2. compute Transpose[G]
  3. call DFS(Transpose[G]), but in the main loop of DFS, consider the vertices in order of decreasing f[u] (as computed in line 1)
  4. output the vertices of each tree in the depth-first forest formed in line 3 as separte strongly connected components.

attachment:SCC.jpg

StronglyConnectedComponents (last edited 2004-10-25 22:44:47 by yakko)