通用图形循环检测(请确认我的答案)

Question

问题是：

如果一个无向图正好包含一个圈，它就是单圈图。描述一种确定给定图G是否为单圈图的O算法。

我的解决方案：

int I=0

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

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

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

Answer 1

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

在这种情况下，只需计数顶点和边，并检查_~_

否则，计算连接组件的数量O(x=0，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，2，5，2，2，2，5，2，5，2，2，2，2，2，2，5，5，5，5，4，4，2，5，5，5，5))的连通分量的数目，并勾选{##**$$}}

备注:有多个连接组件与您的算法相反。

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