使用DFS和雙組分算法查找關節點

Question

我在執行（不是代碼）DFS時遇到了麻煩，該算法結合雙組分算法來查找圖中的關節點，該算法在我的計算機科學講座中提出，沒有把握實施。 （只是爲了澄清我知道如何實現DFS）讓我解釋一下：我們給出了一個圖表，我們必須執行一個DFS來查找所有關節點，使用後面的數字和DFS號碼。我的主要問題是使用給定的算法找到每個節點的背部編號。

我們給了一個教程作爲練習來實現算法，我做了它，但我不知道它是否正確。有人可以檢查我是否做得正確，如果可能的話糾正我。教程問題如下

使用類中的算法做一個 深度優先搜索樹的算法。對於每個頂點發現：

•在DFS-數

•背號

•它是否是一個關節點 算法和我的解決辦法是： 感謝。希望有人可以幫助

Answer 1

你算法幾乎是正確的。處理不當的唯一情況是根：當且僅當在dfs樹中有兩個或更多子項時，根纔是關節點。