廣度優先遍歷樹，巨蟒

Question

我想通了深度優先遍歷樹。

def _dfs(tree, res): 
    if tree: 
     res += [tree.key] 
     _dfs(tree.left, res) 
     _dfs(tree.right, res) 
    return res 

我似乎無法找到廣度優先搜索解決方案。將不得不使用隊列或堆棧？

謝謝！

Answer 1

是的，你必須使用一個隊列來保存您檢查過，但還沒有遞歸到節點。

從隊列中的根節點開始，然後重複[彈出一個節點併爲其每個子節點執行所需的任何操作（res += [tree.key]）並將其推送到隊列中]。

Answer 2

你可以用雙端去。這是一個經典的實現（使用FIFO隊列）從馬格努斯烈赫特蘭的高爐。

from collections import deque 

def bfs(G, s): 
    P, Q = {s: None}, deque([s]) 
    while Q: 
     u = Q.popleft() 
     for v in G[u]: 
      if v in P: continue 
      P[v] = u 
      Q.append(v) 
    return P