如果形成一個循環的一條邊是已知的，則列出在一個圖中形成一個循環的所有邊的最快方法

Question

我一直在尋找在無向圖中尋找形成循環的邊的算法（尤其是：http://www.geeksforgeeks.org/detect-cycle-undirected-graph/）。我問的是：有沒有快速的方法來找到這樣一個循環，如果一個邊已知？（只有一個這樣的循環）我想到的僅僅是在形成邊的兩個頂點上應用isCyclicUtil（或也許只有一個），並使用訪問陣列來檢查形成它的邊緣。有沒有更快的方法解決這個問題。任何人有任何想法？

Answer 1

由於A和B是雙連接頂點，因此可以刪除它們之間的邊並運行DFS/BFS以在它們之間找到路徑。這條路徑確實是原始圖形中的一個循環（具有刪除的邊緣）。