Python構造BFS

Question

我在網上發現了很多BFS示例代碼，但是輸入的格式與我的格式不一樣，輸出結果也不像預期的那樣。

我有節點nodesList的列表，每個節點對象都有一個節點id幷包含在neighboursList它的鄰居節點的所有id。現在我想用nodesList構建一個BFS。正如我知道計算可以完成並且被構造一個BFS如果我知道：

• 哪些節點是在BFS的每個級別（級別1）：根，等]的

• 父節點在每個節點的BFS

• 子節點在BFS

• 的節點的每個節點在BFS

每個節點的節點210 id所以我創建了另一個類中調用BFSnode，存儲我需要的信息。雖然我總是可以找出前兩個級別，但我不知道輸入圖形的大小，我很困惑，我怎樣才能使用遞歸動態地查找這些級別。由於我不熟悉動態編程和遞歸，如果有人能幫助我，我將不勝感激。非常感謝。

Answer 1

要做廣度優先搜索，您不需要使用遞歸或動態編程。

廣度優先搜索通常使用隊列數據結構：
1.首先將根節點或要開始搜索的節點添加到隊列中。
2.隊列中有節點時，首先將下一個節點出列。處理它，但你需要和排隊的孩子。
3.當隊列爲空時，搜索結束。

粗糙代碼（未測試）：

class Node(object): 
    def __init__(self, val): 
     self.val = val 
     self.children = [] 

def breadth_first_search(root): 
    next_nodes = Queue() 
    next_nodes.enqueue(root) 

    while not next_nodes.empty(): 
     cur_node = next_nodes.dequeue() 

     # Do something with cur_node 

     for child in cur_node.children: 
      next_nodes.enqueue(child) 

我假定支持入隊，出隊，並且空隊列對象，它是未在python一個內置的存在。您可以編寫自己的，使用列表或使用append（）和popleft（）而不是入隊和出隊的collections.deque。

我也假定圖形沒有周期。看起來你正在處理樹木，所以這可能是一個安全的假設。