有没有一种方法可以在线性时间内找到图中属于简单循环的所有顶点？
我找到了一种在 O(|V|(|V|+|E|)) 时间内完成的方法，但想知道是否有办法更快？
您想要做的是删除所有桥（即删除时断开组件的边缘）。维基百科文章提供了两种查找所有桥梁的算法 - Tarjan 算法 和 Schmidt 算法 - 两者都是线性时间的。
一旦所有的桥都消失了，每个节点要么是孤立的（度数为 0），要么是循环的一部分。扔掉孤独的节点，剩下的就是你想要的节点。
使用DFS（深度优先搜索），您可以在O(|V|+|E|)时间内完成。在实现DFS时，只需保留您一直在跟踪其父节点的vertives的记录，一旦您发现子节点与父节点相同（意味着循环完成），您就可以声明从该父节点到最后一个子节点的所有节点作为一些简单循环的一部分。
如果您需要更多解释，请在下面评论。
我喜欢 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 的顶点，则意味着你有一个循环。要在循环上查找顶点，请使用前驱数组来存储路径中的前一个顶点。
好吧，我想我已经有了答案。 在处理 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|)。