通用图形周期检测(请确认我的答案)

Question

问题：

如果无向图只包含一个循环，则它是单环图。描述 O（ |V|+ |E|）算法，用于确定给定图G是否为单环。

我的解决方案：

整数 i = 0

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

DFS 完成后，如果 i==1，则图形为单环。

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

Answer 1

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

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

否则计算连接的组件数 O（|V|+ |E|），并检查 |V|- |E|= 连接的组件数 - 1。

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

Answer 2

"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