假设我们在有向图上运行 sharir kosaraju 算法。我们在这张图上有一条弧 (u,v)。 在这个算法中，我们有两个 DFS 通过。 现在假设我们将顶点 u 插入到第一棵深度树 T 中。 v 可以出现在哪里？它是在另一棵更早或更晚创建的树中吗？ 提前致谢!
我正在为考试而学习...所以我猜这是一种家庭作业，但我真的不知道!
最佳答案
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。
关于algorithm - sharir kosaraju 算法和顶点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10063015/