我不明白這個算法是如何告訴我一個圖是否是雙連通的

Question

我正在爲即將到來的面試做一些練習，並且我發現一個練習題要求O（V + E）算法來告訴我圖形是雙連通的。 This普林斯頓的一頁說，如果一個圖沒有關節頂點，其中一個關節頂點是一個頂點，其移除將增加連接組件的數量（因爲雙連接圖應該有一個連接組件），則該圖是雙連通的。

該問題的一個常見解決方案是使用附加跟蹤來查看是否有任何頂點是關節頂點。 This頁說，頂點是關節的頂點，如果

• V是具有至少2名兒童 或
• 伏的根節點有一個孩子不能達到V的祖先

然而，根節點的條件對我來說沒有意義。下面是一個雙連通圖的例子：如果我們選擇任何一個節點作爲根，它們都有2個或更多的子節點，所以將是一個節點頂點，從而使圖不會雙連通。這是查找連接組件的常用算法，因此假定我誤解了某些內容。我真的需要檢查根節點以查看圖形是否是雙連通的？

Answer 1

你應該做深度優先搜索，這意味着DFS樹總是看起來像

1 4 
| | 
2---3 

因爲直到大功告成探索一切，可你不能探索1--4鏈接沒有經過1而從2達到，並且您不會添加1--4，因爲它會在樹邊緣形成一個循環。此樹中沒有節點有兩個孩子（1是根）。