我学习Kosaraju算法从这里 Kosaraju寻找强连通分量算法。 但我不明白是什么做的DFS（G ^ T）递减顺序整理倍的必要性IE提到在上面的链接点3。

I am learning Kosaraju algorithm for finding strongly connected components from here Kosaraju algorithm . But I can't understand what is the necessity of doing dfs(G^T) in decreasing order of finishing times i.e mentioned in Point 3 in above link.

推荐答案

考虑与两个顶点A和B以及从B到A（以G ^ T或A到B）一个边缘的简单图形。如果你做的顶点DFS（G ^ T），以A则B则输出这是一个强连通分量。而应该是两个独立的组件。

Consider a simple graph with two vertices A and B and one edge from B to A (or A to B in G^T). If you do dfs(G^T) on the vertices in order A then B then you output this as a single strongly connected component. Whereas it should be two separate components.

非正式的，做的顶点指定顺序的必要性，以确保您只去上下G链接第一个G ^ T链接时，你也可以去。

Informally, the necessity of doing the vertices in the specified order is to ensure you only go "up" G^T links when you can also go "down" G links first.