2

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 。

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

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

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

4

1 回答 1

2

IMO 这两种算法是等价的，但略有不同。不同之处在于它们输出的 SCC（强连接组件）的顺序。

假设我们有一个无环有向图，其 SCC 依次为 S1、S2、S3、S4。

S1 -> S2 -> S3 -> S4

算法 1（维基百科）。

当你构建栈 S 时，对于任何顶点 v，所有在 v 之后的顶点都应该在 v 之前进入栈 S，因为我们是在前向图上进行 DFS。

现在我们反转图形：

R_S1 <- R_S2 <- R_S3 <- R_S4

要从 Stack 中弹出的第一个顶点S应位于R_S1. 因此，当您执行 DFS 时，要输出的第一个 SCC 应为R_S1.

算法 2（书）。

这里我们首先反转图形：

R_S1 <- R_S2 <- R_S3 <- R_S4

现在，当我们对任何顶点进行 DFS 时v，（在原始图中）之前的顶点v应在 v 之前排序。此外，由于我们从 order_index 开始N然后递减 order_index，因此之后的所有顶点v都应具有较低的拓扑排序比 v.

原图：

S1 -> S2 -> S3 -> S4

最低排序的顶点现在应该在S4. 因此，将从图中输出的第一个 SCC 应与第一种情况S4相反。R_S1

于 2014-05-31T04:39:51.317 回答