algorithm - 为什么我们需要在 Kosaraju 算法中的图的补集上运行 DFS？

Question

有一个著名的求强连通分量的算法叫做 Kosaraju 算法，它使用两个 DFS 来解决这个问题，并在 θ(|V| + |E|) 时间。

首先，我们对图 (G^R) 的补集使用 DFS 来计算顶点的反向后序，然后我们应用第二个 DFS在主图 G 上，通过以反向后序获取顶点来计算强连通分量。

虽然我了解算法的机制，但我并没有得到反向后序需求背后的直觉。

它如何帮助第二个 DFS 找到强连通分量？

Answer 1

假设第一个DFS的结果是:

----------v1--------------v2-----------

其中“-”表示任意数，强连通分量 g 中的所有顶点都出现在 v1 和 v2 之间。

DFS 邮寄订单提供以下保证

• v2之后的所有顶点在反向图中都不会指向g(也就是说，你不能从g到达这些顶点在原始图中)
• v1之前的所有顶点在逆向图中不能从g指向(也就是说，你不能从这些顶点到达g原始图中的顶点)

简而言之，第一个 DFS 确保在第二个 DFS 中，较早访问的强连通组件不能与其他未访问的强连通组件有任何边缘点。

一些详细的解释

让我们简化图表如下:

• 整个图是G
• G包含两个强连通分量，一个是g，另一个是单顶点v
• 在v和g之间只有一条边，要么从v到g，要么从g到v，这条边的名字是e
• g', e' 代表g, e

该算法可能失败的情况可以总结为

1. 从v开始DFS，e'从v指向g'
2. 从g'内部的一个顶点开始DFS，e'从g'指向v

对于情况 1

原始图类似于 g-->v , 反转图看起来像 g'<--v .

要从 v 开始第二个 DFS，第一个 DFS 生成的后序需要类似于

g1, g2, g3, ..., v

但是你会很容易发现从v开始第一个DFS和从g'开始都不能给你这样的后序，所以在这种情况下，它是保证第一个 DFS 第二个 DFS 不会从既不在强连通分量又指向强连通分量的顶点开始。

对于情况 2

与情况一类似，在情况二中，原图为g<--v而相反的是g'-->v ，保证 v 会在 g' 中的任何顶点之前被访问。