找到属于简单循环的所有顶点

Question

有没有办法在线性时间内找到图中简单循环一部分的所有顶点？

我在O(| V |(| V | + | E |))时间找到了一种方法,但是想知道是否有办法更快地完成它？

Answer 1

您要做的是移除所有桥(即移除时断开组件的边缘).维基百科文章提供了一种用于查找所有桥梁的线性时间算法.

一旦所有桥都消失,每个节点要么被隔离(具有0度),要么是循环的一部分.抛弃孤独的节点,剩下的就是你想要的节点.

Answer 2

好吧，我想我已经有了答案。在处理 DFS 时，对于每个顶点 v 计算 low(v)（如下所述）。然后再次运行 DFS 并检查每个顶点 v：

if low(v) != d(v) （其中 d(v) 是距 DFS 树根的距离）

顶点 v 是简单循环的一部分。

*low(v) = min ( d(v),d(u),low(w)) 其中 (v,u) 是后边缘，w 是 DFS 树中 v 的子节点。计算时间为 O(|V|+|E|)。