graph - 通用图循环检测（请确认我的答案）

Question

问题：

如果无向图恰好包含一个环，则它是单环的。描述一个 O( |V| + |E| ) 算法，用于确定给定图 G 是否是单环的。

我的解决方案：

整数 i = 0

在 G 上运行一个修改后的 DFS，每次我们决定不访问某个顶点时都会增加 i，因为它已经被访问过。

DFS 完成后，如果 i==1，则图是单环的。

我认为这个解决方案会起作用，但我想知道是否有一个反例可以证明它是错误的。如果有人能澄清一下，那就太好了，谢谢。

Answer 1

"Increment i everytime we decide not to visit a vertex because 
it has already been visited."

我很不清楚你想在这里做什么。

而不是这个，这个怎么样：

执行 DFS 并计算后边缘的数量。

A back edge is an edge that is from a node to itself (selfloop) or one of its 
ancestor in the tree produced by DFS.

如果后边数 ==1 则为独轮车，否则不是。

To count number of back edges, follow this algorithm.

To detect a back edge, we can keep track of vertices currently in recursion stack of 
function for DFS traversal. If we reach a vertex that is already in the recursion stack,
then there is a cycle in the tree. The edge that connects current vertex to the
vertex in the recursion stack is back edge

Answer 2

您的图表是否由单个连接组件组成？

在这种情况下，只需计算顶点和边并检查 |V| - |E| = 0

否则计算连通分量的数量 O(|V| + |E|)，并检查 |V| - |E| = 连接组件的数量 - 1。

备注：具有多个连接组件是您算法的反例。