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.