廣度優先搜尋（BFS）教學：原理、程式碼與時間複雜度

BFS 解決什麼問題

許多問題其實都是圖：網頁與連結、社群網路中的朋友、棋盤上的格子、謎題的各種狀態。對這類圖，BFS 能回答兩個常見問題：從起點出發可以到達哪些節點？到達每個節點最少需要幾步？

BFS 是以距離遞增的一圈圈範圍向外探索，所以第一次到達某個節點時，走的一定是邊數最少的路徑。因此當每條邊的成本相同時，BFS 就是求最短路徑的標準演算法。

用白話說明原理

1. 把起點放進佇列，並標記為已拜訪。
2. 取出佇列最前面的節點。
3. 對每個尚未拜訪的鄰居，標記為已拜訪，並加到佇列尾端。
4. 重複步驟 2 和 3，直到佇列為空。

請在節點加入佇列時就標記為已拜訪，而不是取出時才標記。否則同一個節點在被處理之前可能被重複加入許多次。

逐步範例

考慮這個無向圖：A–B、A–C、B–D、C–D、C–E、D–F。從 A 出發，並依字母順序拜訪鄰居。

拜訪順序是 A、B、C、D、E、F。B 和 C 都能到達 D，但 D 只會被發現一次（從 B 發現），因為當下它就已被標記為已拜訪。

Python 實作

佇列請使用 collections.deque：popleft() 是 O(1)，而 list.pop(0) 是 O(n)。圖以字典表示，每個節點對應到一個鄰居串列（鄰接串列）。

from collections import deque
def bfs(graph, start):
    """Return the distance (number of edges) from start to each reachable node."""
    dist = {start: 0}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for nxt in graph[node]:
            if nxt not in dist:          # not visited yet
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
    return dist
graph = {
    "A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D", "E"],
    "D": ["B", "C", "F"], "E": ["C"], "F": ["D"],
}
print(bfs(graph, "A"))  # {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 2, 'F': 3}

這裡的 dist 字典身兼兩職：既是已拜訪集合，也儲存答案。若要重建實際路徑，只要另外記錄每個節點的父節點，再從目標往回走即可。

def shortest_path(graph, start, goal):
    parent = {start: None}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node == goal:
            path = []
            while node is not None:
                path.append(node)
                node = parent[node]
            return path[::-1]
        for nxt in graph[node]:
            if nxt not in parent:
                parent[nxt] = node
                queue.append(nxt)
    return None  # goal not reachable
print(shortest_path(graph, "A", "F"))  # ['A', 'B', 'D', 'F']

時間與空間複雜度

V 是頂點（節點）數，E 是邊數。若改用鄰接矩陣而非串列，時間會變成 O(V²)，因為找出一個節點的鄰居需要 O(V)。

變化版本與常見錯誤

• 網格 BFS：把每個格子視為節點，上下左右（或八個方向）的相鄰格子視為邊。加入格子前要先檢查邊界與牆壁。
• 多源 BFS：把多個起點以距離 0 一起放進佇列，可求出到最近起點的距離，例如迷宮中最近的出口。
• 0-1 BFS：當邊權重只有 0 或 1 時，使用雙端佇列，並把權重為 0 的鄰居推到前端，即可在 O(V + E) 內求出最短路徑。
• 雙向 BFS：同時從起點和終點開始搜尋，兩邊的搜尋前線相遇時停止，通常能少探索許多節點。
• 逐層處理：每一輪開始時記錄 len(queue)，並剛好取出這麼多個節點，就能一次處理一整層。

何時使用 BFS 與實際應用

• 面試題目：迷宮或網格中的最短路徑、單字接龍（word ladder）、腐爛的橘子（多源 BFS）、二元樹的層序走訪、騎士的最少步數。
• 網路應用：找出 k 跳以內的所有裝置、點對點網路中的廣播、社群圖中距離為 2 的「你可能認識的人」。
• 網路爬蟲，依與起始頁面的連結距離順序拜訪網頁。
• 垃圾回收器（例如 Cheney 複製式回收器）以及需要最少步數的解謎程式。