algorithm - 使无向图成为强连通分量(SCC)

Question

Let G(V,E), an undirected, connected graph with no bridges at all. Describe an algorithm which direct the edges, so the new graph is an SCC.

我推荐的算法
所以我们从任意顶点运行 DFS。我们注意到，由于它是一个无向图，因此只有树边和后边(对吗？)。我们相应地连接边(树边将指向“向下”，后边将指向“向上”)。

证明的开始
我们注意到该图没有桥。因此，每条边都是某个循环的一部分。因此，某个循环中最后被发现的边一定是后边。

现在，我认为其余的证明需要证明我们总是可以“爬”到根，因此该图是一个 SCC。

如果你能帮我连接点(或顶点 XD)，我会很高兴

谢谢

Answer 1

您正在寻找的是 Robbins' Theorem 的证明.
有关更正式的证明，您可以查看 this paper (见定理 2 的证明)。

以下不是正式的证明，但这是您可以想到的一种方式:

正如您已经提到的，由于没有桥，每条边都是某个循环的一部分。由于您希望输出图为 SCC，因此此输出图(来自任何顶点)上的 DFS 必须仅具有back-edges 和tree-edges。它不能有forward-edges 或cross-edges。

假设我们有一条从s 到t 的forward-edge。这意味着在我们为了构建图形而运行的 DFS 中，t 是在 s 的子 DFS(递归调用)中发现的，并且没有其他灰色或白色相邻的。但这不是真的，因为每当我们在 DFS 中发现 t 时，我们仍然会有灰色相邻。

假设我们有一条从 s 到 t 的交叉边。这意味着 t 的子 DFS 在 s 被发现之前已经结束。同样，这在我们的 DFS 中不会发生，因为当首先发现 t 时，我们会在其子 DFS 或相反方向发现 s。

这是一个简单的图表，可以帮助您了解这些情况。