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

Question

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

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

尽管我了解算法的机制，但我并没有得到反向发布顺序需要背后的直觉。

它如何帮助第二个 DFS 找到强连接组件？

Answer 1

假设第一个 DFS 的结果是：

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

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

DFS by post order 提供以下保证：

• 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 的顶点开始be out of and 指向一个强连通分量。

对于情况 2

与情况 1 类似，在情况 2 中，原图为g<--v且反转为g'-->v，保证v将在g ' 中的任何顶点之前被访问。

Answer 2

1. 当您第一次在图上运行 DFS 时，对于您访问的每个节点，您都会了解可从该节点访问的所有节点（您会在第一个 DFS 完成后获得此信息）。

2. 然后，当您反转所有顶点并再次运行 DFS 时，对于您访问的每个节点，您都会获得有关非反转图中可以到达该节点的所有节点的知识（同样，您会在第二个 DFS 完成后获得此信息）。

示例：假设您的第一个 DFS 到达节点 X。从该节点“您可以看到”您可以访问的所有邻居。（我希望这是可以理解的）。然后，假设您的第二个 DFS 到达该节点 X，但这次所有顶点都被反转了。如果然后从您的节点 X “您可以看到”任何其他节点，则意味着在反转顶点之前，节点 X 可以从您现在看到的所有邻居访问。通过以正确的顺序调用第二个 DFS，您可以为每个节点 X 获得两个 DFS 树中可以从 X 到达的所有节点（因此，对于每个节点 X，您可以获得既可以从 X 到达又可以到达 X 的节点 -根据定义，它们是强连接的组件）。

Answer 3

假设列表L是节点的后序 DFS 访问。u->v表示存在从u到的转发路径v。

如果u->v与否v->u，则u必须出现在in的左侧。然而， SCC 中的节点，例如和，可以以任意顺序出现在列表 中。vLvwL

因此，如果一个节点x严格出现y在列表之前L：

• case1:x->y和y->x，就像和的情况v一样w
• case2: x->yand not y->x，就像uand的情况v
• 案例3：不是x->y和不是y->x

LKosaraju 的算法从左到右迭代并从转置图上的每个节点开始运行 DFS（其中边的方向被反转）。如果某个节点可以被 DFS 访问，并且它不属于任何 SCC，那么我们将该节点添加到当前根的 SCC。

在案例 1 中，我们将添加y到x. 在案例 3 中，y并且x在不同的 SCC 中。

案例 2 需要特别注意。在我们调用 DFS 的时候y，x已经在其他一些 SCC 中了，所以我们不会添加x到 的 SCC 中y。想象一下，如果你在从 rooty开始的 DFS 之前调用了从 root 开始的 DFS x，那么x会被添加到 的 SCC 中y，这是错误的。

简而言之，第一个 DFS 将那些可以到达y但不能到达的节点排列y在其左侧。因此第二个 DFS 能够避免将此类节点添加x到y.