2
$\begingroup$

I was trying to implement an algorithm which finds the strongly connected components (SCC's) of a directed graph. In order to find the SCC's, as the last step we need to be able to generate the Depth-First Search Forest as mentioned in CLRS:

STRONGLY-CONNECTED-COMPONENTS (G)

 1. Call DFS(G) to compute finishing times f[u] for all u.
 2. Compute G^T
 3. Call DFS(G^T), but in the main loop, consider vertices in order of decreasing f[u] (as computed in first DFS)
 4. Output the vertices in each tree of the depth-first forest formed in second DFS as a separate SCC.

However, I did not understand how to generate the DFS Forests from the Depth First Search. Please explain me how is it possible, and preferably use Cormen's DFS Psuedocode as I am a beginner and am quite familiar with CLRS.

Below is Cormen's DFS psuedocode:

DFS (V, E)

1.     for each vertex u in V[G]
2.        do color[u] ← WHITE
3.                π[u] ← NIL
4.     time ← 0
5.     for each vertex u in V[G]
6.        do if color[u] ← WHITE
7.                then DFS-Visit(u)              ▷ build a new DFS-tree from u



DFS-Visit(u)

1.     color[u] ← GRAY                         ▷ discover u
2.     time ← time + 1
3.     d[u] ← time
4.     for each vertex v adjacent to u     ▷ explore (u, v)
5.        do if color[v] ← WHITE
6.                then π[v] ← u
7.                        DFS-Visit(v)
8.     color[u] ← BLACK
9.     time ← time + 1
10.   f[u] ← time                                 ▷ we are done with u

PS: Rest assured, this is not homework.

$\endgroup$

1 Answer 1

1
$\begingroup$

Algorithm DFS-Visit(u) finds a tree that consists of vertices that are in the same connected component as vertex u. Basically, when you run DFS-Visit(u), you visit every vertex in the same connected component as u and you change their color to black.

In algorithm DFS(V, E), in steps 5-7, you find a vertex u with color white (which means that it is not in any of the previous trees/visited connected components) and run DFS-Visit(u) in order to find the next tree.

$\endgroup$
3
  • $\begingroup$ It finds the connected components indeed but not the strongly connected components. $\endgroup$ May 21, 2016 at 11:09
  • $\begingroup$ @DanishAmjadAlvi As you mentioned, it finds a forst. Where did you come to conclusion that it finds a strong connected component? Where in your question you mentioned that you are looking for SCC? $\endgroup$
    – orezvani
    May 22, 2016 at 1:55
  • $\begingroup$ Absolutely I had not mentiooned. :) $\endgroup$ May 22, 2016 at 2:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.