Python的迭代深度優先搜索，從表

Question

，我有以下數據表：

child_pid parent_pid 
     1  -1 
     2   1 
     6  -1 
     7   6 
     8   7 
     9   8 
     21  -1 
     22  21 
     24  -1 
     25  24 
     26  25 
     27  26 
     28  27 
     29  28 
     99  6 
     107  99 
     108  -1 
     109  108 
     222  109 
     1000  7 
     1001  1000 

我想寫一個python迭代深度優先搜索產生以下結果：

('final: ', 
    [[u'1', u'2'], 
    [u'6', u'7', u'8', u'9'], 
    [u'6', u'7', u'1000', u'1001'], 
    [u'6', u'99', u'107'], 
    [u'21', u'22'], 
    [u'24', u'25', u'26', u'27', u'28', u'29'], 
    [u'108', u'109', u'222']]) 

以上輸出是使用遞歸方法生成的。我們可以看到，所有的孩子/父母關係都得到適當保存。

我已經利用從另一個教程以下邏輯在我試圖得到一個迭代的方法：

def dfs_iterative(graph, start): 
    stack, path = [start], [] 

    while stack: 
     vertex = stack.pop() 
     if vertex in path: 
      continue 
     path.append(vertex) 
     for neighbor in graph[vertex]: 
      stack.append(neighbor) 

    return path 

導致：

('final: ', 
    [[u'1', u'2'], 
    [u'6', u'99', u'107', u'7', u'1000', u'1001', u'8', u'9'], 
    [u'21', u'22'], 
    [u'24', u'25', u'26', u'27', u'28', u'29'], 
    [u'108', u'109', u'222']]) 

我們可以看到，結果幾乎是相同的除非節點有多個孩子。具體地，節點6具有以下關係：

6->7->8->9 
6->7->1000->1001 
6->99->107 

在遞歸輸出以上，我們看到，節點6被適當地分解成它的正確的路徑的關係。在我的迭代嘗試中，節點6的所有「後代」都被組合在一起。尋找方式來產生遞歸輸出，但在python中使用迭代方法。思考？我感謝幫助！

Answer 1

這裏的問題是你的迭代「等價」不是：你的算法找到圖閉包。你想要的結果是在樹中查找單個路徑。當你使用錯誤的工具時，你會得到不同的結果。

您的方法似乎開始於給定節點（表面上是根節點之一），並以鄰居未定義的順序累積單個節點。相反，試試這個

• 從棧中彈出頂部partial_path
• 頂點 <;最後一個元素
• 如果頂點的partial_path有沒有孩子：
  • 追加partial_path導致。
• 別的
  • 爲頂點
  • 添加（附加或推）的每個子[partial_path + 子]堆疊

這是否處理你的問題？