有没有办法在线性时间内找到图中简单循环的一部分的所有顶点？
我找到了一种在 O(|V|(|V|+|E|)) 时间内做到这一点的方法，但想知道是否有一种方法可以更快地做到这一点？
问问题
5243 次
4 回答
10
您想要做的是移除所有的桥（即移除时断开组件的边）。维基百科文章给出了一个线性时间算法来寻找所有的桥梁。
一旦所有的桥都消失了，每个节点要么是孤立的（度数为 0），要么是循环的一部分。扔掉孤独的节点，剩下的就是你想要的节点。
于 2013-07-05T20:56:29.727 回答
2
使用 DFS（深度优先搜索），您可以在 O(|V|+|E|) 时间内完成。在实现 DFS 时，只要找到与父节点相同的子节点（意味着循环的完成），您就可以使用父节点跟踪您一直在跟踪的 vertives 的记录，您可以声明从该父节点到最后一个子节点的所有节点作为一些简单循环的一部分。
如果您需要更多解释，请在下方评论。
于 2013-07-05T10:19:00.433 回答
0
我喜欢 Bhavya 的回答：但如果我详细说明它会有所帮助。
通常，如果您执行 DFS，您有一个访问过的数组，该数组包含已访问/未访问状态。
现在有
int visited[N];//N is the number of nodes/vertices in graph
让
visited[i] =-1 if i-th vertex is not yet visited
visited[i] = 0 if i-th vertex is being processed
visited[i] = 1 if processing of i-th vertex is done
这样，如果您在dfs中遇到访问值为0的顶点，则表示您有一个循环。要在循环上查找顶点，请使用前驱数组来存储路径中的前一个顶点。
于 2013-07-05T11:01:28.383 回答
0
好吧，我想我有答案了。在处理 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|) 时间内计算。
于 2013-07-06T08:06:50.757 回答