algorithm - 在 Kosaraju 算法中以完成时间的递减顺序进行 DFS 以查找强连接组件的必要性是什么？

Question

我正在学习 Kosaraju 算法以从这里找到强连通分量 Kosaraju algorithm .
但是我不明白按照完成时间的递减顺序执行 dfs(G^T) 的必要性是什么，即上面链接中第 3 点中提到的。

Answer 1

考虑一个简单的图，它有两个顶点 A 和 B，一条边从 B 到 A(或 G^T 中的 A 到 B)。如果您按 A 然后 B 的顺序在顶点上执行 dfs(G^T)，那么您将其输出为单个强连通分量。而它应该是两个独立的组件。

通俗地说，按指定顺序处理顶点的必要性是为了确保您只“向上”G^T 链接，同时您也可以先“向下”G 链接。