algorithm - 寻找强连通分量 - Kosaraju 算法

Question

在有向图中，要找到强连通分量(使用 Kosaraju 算法)，如果我们可以在完成时间之前使用节点的反向列表然后遍历原始图，为什么我们必须转置邻接矩阵(反转所有边的方向) .换句话说，我们会找到所有顶点的完成时间并开始从最低完成时间遍历到最大(通过增加完成时间)？

此外，如果我们对某些 DAG 进行拓扑排序，然后反转边(转置邻接矩阵)并再次进行拓扑排序 - 我们是否应该以相反的顺序得到相等的数组？

Answer 1

这不会给 SCC。考虑 2 个子图 S1 和 S2。为了使 S1 和 S2 都成为单个 SCC 的一部分，应该有一条从 S1 到 S2 以及从 S2 到 S1 的路径。按照您提到的方式，即使只有从 S1 到 S2 的路径，它也会将它们计为单个 SCC。原始图和反向图上的 DFS 确保只有在两个方向上都有路径的组件才会在 SCC 内组合。

Additionally, if we do topological sorting on some DAG, and then reverse edges (transpose adjacency matrix) and do topological sorting again - should we get to equal arrays, just in reversed order?

不一定。考虑一个简单的例子 (1->2,1->3) .Topological sort=(1,2,3)。反转图(2->1,3->1)。拓扑排序(2,3,1)