無向圖中的循環數

問題與標題所示相同，該圖以鄰接列表形式給出。我的方法是在任何一個頂點調用DFS，並且每當我在DFS遞歸步驟中訪問頂點時，我將從0開始遞增全局變量的計數器，並且不會爲該訪問頂點調用DFS（正如我們通常所做的那樣）。這是否正常工作，我想對嗎？我還沒有在互聯網上找到任何相關文章，以瞭解＃無向圖中的循環次數。無向圖中的循環數

詳細說明：我的意思是使用簡單的DFS方法。雖然我們在遇到訪問頂點的遞歸步驟中沒有做任何事情，但我增加了該情況下的全局變量值counter。我這樣做，因爲每當我遇到一個訪問過的頂點，就意味着我正在完成一個循環。我聲稱：在任何DFS運行中，圖中的每個週期只遇到一次（至少和最後一次）。 AM我在本索賠中糾正了嗎？

編輯：無後邊緣

來源

2017-04-22 Akash

我假設你的意思是*簡單*週期的數量？另外，請提供更多詳細信息，根據我對你的建議的理解，你也會在發現* cross edge時增量* – amit

Ya我的意思是簡單請參閱問題中的詳細說明。 – Akash

[查找無向圖中的所有循環。]（http://stackoverflow.com/questions/12367801/finding-all-cycles-in-undirected-graphs） – Dukeling

對不起張貼答案，我的答案本身，只是對於那些誰在未來也有類似的疑問：我發現我要進行冗餘計算多個週期，爲如： -

A 
/ \ 
B ----- C 
    \ /
    D

從A-> B-> C-> DI啓動DFS獲取週期CBD計數兩次。我還了解到在無向圖中查找所有循環的問題是非常困難的。「（

來源

2017-04-22 10:35:33 Akash

'我很抱歉地將答案發布給我自己的答案'不要這樣，那很好：https：//stackoverflow.com/help/self-answer – amit

無向圖中的循環數

回答

相關問題