SCC

powered by FreeFind

Modified: 
Strongly-Connected-Components (G)
1    Call DFS (G) to compute finishing times f[u] for each vertex u
2 Compute GT
3 Call DFS (GT), 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 a separate strongly connected component. 
Do this by starting with the smallest f[u] value (from GT) and use the predecessor array p, from GT
Components that are connected in G are still connected; e.g. (abe, cd) since G contains (b, c).

DFS(G) is given below.

    

  1. Complete the table for G.
  2. Give f[u] in decreasing order.
  3. Draw GT.
  4. Find DFS(GT), but in the main loop of DFS at Line 5, consider the vertices in order of decreasing f[u]. Assume that the adjacency list is ordered alphabetically at Line 4 of DFS-Visit.
  5. On the graph above, circle GSCC
G   a   b   c   d   e   f   g   h
d                
f                
p                
GT   a   b   c   d   e   f   g   h
d                
f                
p                
DFS (G)
1  for each vertex u Î V[G] do
2    color[u] ¬ WHITE
3    p[u] ¬ NIL
4  time ¬ 0
5  for each vertex u Î V[G] do
6     if color[u] = WHITE then
7        DFS-Visit (u)
DFS-Visit (u)
1       color[u] ¬ GRAY
2 time ¬ time + 1
3 d[u] ¬ time
4 for each vertex v Î Adj[u] do
5    if color[v] = WHITE then
6       p[v] ¬ u
7       DFS-Visit (v)
8 color[u] ¬ BLACK
9 f[u] ¬ time ¬ time + 1