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

Question

有一个著名的算法来寻找强连通分量Kosaraju's algorithm，它使用两个 DFS 来解决这个问题，并且?(|V| + |E|)及时运行。

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

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

它如何帮助第二个 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开始还是从g'开始第一个 DFS 都不能给你这样的后序，所以在这种情况下，保证第一个 DFS 不会从第一个 DFS 开始，第二个 DFS 不会从两个顶点都开始出自并指向强连通分量。

对于情况2

与情况1类似，在情况2中，原图是g<--v，逆图是g'-->v，保证v会在g '中的任何顶点之前被访问。