一般圖循環檢測（請確認我的答案）

Question

問題：

如果一個無向圖只包含一個循環，則它是單圈。描述用於確定給定圖G是否是單圈的O（| V | + | E |）算法。

我的解決辦法：

INT I = 0

運行修改DFS上G，我們增加我每次我們決定，因爲它已經被訪問不能訪問的頂點。

DFS完成後，如果我== 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