BFS

BFS 是廣度優先搜索（Breadth-First Search）的縮寫。BFS 用在尋找從起點node到目標node的最短路徑。

相比於DFS是深度優先，BFS是找完第一層找第二層、第三層…，直到寶最後一層，找到目標節點或者所有節點都被遍歷完成。在 BFS 中，節點的訪問順序是按照node到起點node的距離來決定的，距離越短的node先被訪問。

執行順序是　8　→　7　→　9　→　5　→　11　→　4　→　6　→　10　→　12

BFS 一定要有一個queue來實現，list或 set之類也沒差，主要是要有一個容器去裝node，用queue的原因是在乎順序。首先將起點節點加入queue，然後重複以下步驟直到queue為空：

1. 從queue中取出一個node
2. 如果該節點是目標node，則返回該node；否則將該node的所有未訪問過的鄰接node加入queue中
3. 標記該node為已訪問

Normal BFS

root ＝nodeA

queue= collections.deque()  # 做一個queue
queue.append(root)          # 加入初始值
 while queue:               # 開頭一定有個while
    node =　queue.popleft() # 每一次都從queue取一個值

    if node is None:
        continue
    # vist
    print(node.val)         
    queue.append(node.left)  # 把下一層資料加入queue
    queue.append(node.right) # 把下一層資料加入queue

BFS 每個node只會被訪問一次，所以時間複雜度為 O(V+E)， V 是node數，E 是邊數。BFS 的空間複雜度為 O(V)，因為需要用一個queue來存儲待訪問的node。

Normal BFS 和Level Order Traversal

Normal BFS 和 Level Order Traversal 的實現方式有些不同。

剛剛以上介紹的是Normal BFS 的實現方式。

Level Order Traversal 是一種特殊的 Normal BFS，通常用於遍歷binary tree。在 Level Order Traversal 中，會從樹的root node開始訪問，首先訪問距離root node最近的node（也就是第 0 層），然後訪問距離root node為 1 的node（也就是第 1 層），以此類推，直到訪問到最深的node。

先將root node加入佇列中，然後重複以下步驟直到佇列為空：

1. 從queue中取出一個node
2. 將目標node的子node加入queue中
3. 訪問目標node

Level Order Traversal

root ＝nodeA

queue = collections.deque()  # 做一個queue
queue.append(root)          # 加入初始值
 while queue:               # 開頭一定有個while
    next_layer =　collections.deque() # 準備下一層的queue
   
    for node is queue:                       # 下一層
        if node is None:
            continue
        # vist
        next_layer.append(node.left)         # 把下一層資料加入下一層的queue
        next_layer.append(node.right)        # 把下一層資料加入下一層的queue
    queue = next_layer                       # 跑下一層

Level Order Traversal 可以保證每一層的node都被訪問一次，且node的訪問順序是按照層來決定的。在實現上，Level Order Traversal 可以使用一個額外的變數來紀錄當前訪問的node層是第幾層，以便區分不同層次的node。