algorithm - sharir kosaraju 算法和顶点

Question

假设我们在有向图上运行 sharir kosaraju 算法。我们在这张图上有一个弧 (u,v)。在这个算法中，我们有两个 DFS 通道。现在假设我们将顶点 u 插入到第一个深度树 T 中。 v 会出现在哪里？它是在较早或以后创建的另一棵树中吗？提前致谢！

我正在为考试而学习......所以我猜这是一种家庭作业，但我真的不知道！

score 2 · Accepted Answer

Kosaraju 的算法基于这样一个事实，即图的转置具有与原始图相同数量的强连通分量 (SCC)。

1) 你有一个图 G 和一个空的 Stack S。

2) 当 S 不包含 G 中的所有节点时，选择一个随机顶点 u 并对 u 进行 DFS。在此 DFS 期间完成对节点 v 的探索后，将节点 v 推入 S。

回到你的问题，如果有一个有向边 (u,v)，v 肯定会在 u 之前插入到堆栈 S 中。但是，在 v 的插入和 u 的插入之间可以有更多的节点。

3）你做G的转置的DFS，通过从堆栈S中弹出顶点，直到S为空。这将为您提供图表 G 中的所有 SCC。

score 0 · Accepted Answer

维基：http ://en.wikipedia.org/wiki/Kosaraju%27s_algorithm很有启发性。我已经实现了算法，它可以在这里找到。

首先要了解的是，在通过后的第一步中堆栈中的顶部元素将是父元素，而在第二步中，它们将更早地弹出并在转置上操作，其中在原始图将在转置中保持强连接。

第一次通过的全部原因是让父母到达堆栈的顶部。

2 回答 2