问题标签 [kosaraju-sharir]

Kosaraju-Sharir 算法的维基百科总结如下：

设 G 为有向图， S 为空栈。

• 而 S 不包含所有顶点。
  • 选择不在 S 中的任意顶点 v。
  • 从 v 开始执行深度优先搜索。每次深度优先搜索完成扩展顶点 u 时，将 u 推到 S 上。
• 反转所有弧的方向以获得转置图。
• 当 S 非空时：
  • 从 S 中弹出顶部顶点 v。
  • 在转置图中从 v 开始执行深度优先搜索。
  • 访问过的顶点集合将给出包含 v 的强连通分量；记录这一点并从图 G 和堆栈 S 中删除所有这些顶点。等效地，可以使用广度优先搜索 (BFS) 代替深度优先搜索。

但是在我的教科书——Sedgewick's Algorithms（第四版）中——它描述了算法的步骤如下：

• 给定一个有向图 G，计算其反向有向图的反向后序。GR ^_
• 在 G 上运行标准 DFS，但以刚刚计算的顺序而不是标准数字顺序考虑未标记的顶点
• 所有顶点的集合...

在最后一步得出的结论是相同的，就像在它之前执行的操作一样 - 但似乎这些操作以不同的顺序给出：维基百科告诉我首先对 G 进行 DFS，然后对其进行转置，执行G ^R上的第二个 DFS ，而我的教科书建议我从转置开始，在 G ^R上做第一个 DFS，在 G 上做第二个 DFS 。

我的主要问题是：我是否正确理解这一点，还是我误解了其中一个或另一个在说什么？

其次：直觉上，这些操作似乎是可传递的，因此这两种“不同的方法”实际上是等价的，并且总是会产生相同的最终结果。我已经在几个有向图上测试了这种直觉，它似乎是正确的——但它是吗？

第三：假设是这样，是否有任何客观理由偏爱其中一个，或者仅仅是偏好问题？

这是我为 Kosaraju 算法所做的代码的第一部分。

代码读取数据并正确形成 Grev 和 G。我已经为迭代 dfs 编写了代码。我怎样才能找到完成时间？我了解使用纸和笔查找完成时间，但我不理解完成时间作为代码的部分？？我该如何实现它。只有在此之后，我才能继续我的下一部分代码。请帮忙。提前致谢。

data.txt 文件包含：

请另存为data.txt。

所以下面是我用于查找图在有向图中是否具有欧拉循环的代码。该代码适用于几种情况（我的主要方法中的注释行有效）。但它确实适用于 g1 图（我的主要方法中未注释的代码）。它说图形（g1）不是欧拉电路，应该是。请帮我找出错误，谢谢

输出为假。请帮忙