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.