通過非遞歸DFS的關節點

Question

我想找到一些方法來通過非遞歸方法找到根是否是關節點。通過遞歸方法，我們可以遞歸地查找根的未連接子節點的數量。但我沒有找到一種方法來做到這一點沒有遞歸。

Answer 1

我能寫一個我認爲可能會起作用的算法。這裏是：

我們有任何頂點的四個狀態。未經審查，訪問，訪問，重新審視。我們保留一個父數組和一個數組，用於保存未連接的子數。

1. 我們繼續從根開始添加頂點，但是我們不彈出父元素。例如，我們將root 1連接到2,3,6,7，然後我們將1 push到堆棧但不彈出它。相反，我們推動其他孩子。而且我們也爲每個元素維護爸爸。例如，2,3,6,7有1個作爲他們的父親。

2. 如果它們是UNVISITED，我們將棧上的節點標記爲VISITING。

3. 如果在任何節點鄰接列表的遍歷期間，我們發現某個元素處於VISITING狀態，我們將其狀態設爲REVISITING，但只有當這個元素不是它的父親時。例如，最重要的是2,3,6,7處於VISITING狀態。現在，如果7的鄰接表爲1，3，5，10，8，12則因爲1是其父親，所以我們不改變1的狀態，我們去3，看它作爲訪問狀態，也它不是7的父親，我們做其狀態爲REVISITING。現在堆棧從下到上依次爲1,2,3,6,7,5,10,8,12。

4. 現在，如果我們遇到任何元素的鄰接表中沒有UNVISITED元素，if這個元素的狀態是VISITING狀態（不是REVISITING），我們加1到其父親的子女總數（初始化爲0）。如果它處於REVISITING狀態，我們忽略爲其父母的孩子號碼加1。此外，我們將這個元素從堆棧中彈出並使其狀態爲VISITED。

5. 漸漸彈出元素我們到達根的孩子（連接或唯一的）。我們通過步驟4檢查以計算根的唯一未連接子項的數量。如果它大於1，那麼root是一個關節點。

該算法看起來有點複雜，但似乎工作。任何建議或問題都歡迎。