I have been reading up on algorithm for finding the strongly connected components in a directed graph $G=(V,E)$. It considers two DFS search and the second step is transposing the original graph $G^T$.
The algorithm is the following :
- Execute DFS on $G$ (starting at an arbitrary starting vertex), keeping track of the ﬁnishing times of all vertices.
- Compute the transpose,
- Execute DFS on $G^T$, starting at the vertex with the latest ﬁnishing time, forming a tree rooted at that vertex. Once a tree is completed, move on to the unvisited vertex with the next latest ﬁnishing time and form another tree using DFS and repeat until all the vertices in $G^T$ are visited.
- Output the vertices in each tree formed by the second DFS as a separate strongly connected component.
My question is :
- What is the intuition behind this middle step of computing a transpose?