algorithm - 具有罗宾斯定理的强方向图算法

Question

我被问到一个类似这样的问题：

使用深度优先搜索和罗宾斯定理，设计和分析一种有效的算法来构造给定无向图 G 的强方向。如果不存在，则在 G 中输出一个桥。

现在，我可以很容易地证明罗宾斯定理，它表明一个图是强定向的当且仅当它没有桥时（即它是 2-edge-connected）。给我的例子与罗宾斯 1939 年的论文中给出的例子相似，该论文描述了他与交通问题和单向街道的同名定理。但是我不知道如何构建这个算法。

（好吧，不是很茫然。如果我们做这样的事情会怎样：运行 DFS，将所有黑色边缘设为一个方向，将所有灰色边缘设为另一个方向。同时，测试每个顶点的 2 边连接性。不过，这纯粹是直觉，我不确定如何定义一致的方向性。）

标签： algorithmgraphdepth-first-search

Answer 1

无向图上的 DFS 只产生树边和后边。将树边缘从祖先定向到后代允许根到达所有其他节点。后边缘应该从后代定向到祖先，因为另一个方向被树边缘覆盖。如果你发现一个子树没有到子树的祖先的后边，那么进入子树的边就是一个桥。否则，通过将当前子树通过某个边重复转义到祖先，从每个节点到根都有一条路径，从而使有向图强连接。