algorithm - sharir kosaraju 算法和顶点

Question

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

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

Answer 1

Kosaraju's Algorithm基于这样一个事实:图的转置与原始图具有相同数量的强连通分量 (SCC)。

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

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

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

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