Graph Algorithms · 01 / 11
BFS廣度優先搜尋
一層一層向外擴散，天生適合找無權圖最短路徑。
用在：最少步數、幾度人脈、爬蟲逐層抓取
時間複雜度O(V+E)
空間複雜度O(V)
難度入門
前置知識Queue、鄰接串列
01為什麼需要它
社群平台的「你可能認識的人」
Facebook 或 LinkedIn 要推薦「好友的好友」。從你出發，走一步是好友，走兩步是好友的好友，走三步的人通常就不推了。
為什麼用它BFS 是唯一天生「一層一層」往外找的走訪方式。第一層看完才看第二層，所以能精確控制「幾度人脈」。
迷宮與地圖的最少步數
掃地機器人要從充電座走到廚房，格子地圖上每一步代價都一樣。遊戲裡的 NPC 尋路、Google Maps 問「最少轉幾次車」也是同一類問題。
為什麼用它在每一步代價相同的圖上，BFS 第一次碰到目標時走過的步數就是最少步數，不需要更複雜的 Dijkstra。
網路爬蟲與訊息擴散
搜尋引擎從首頁出發抓網頁：先抓首頁上的所有連結，再抓那些頁面上的連結。傳染病模型、網路廣播封包也是同樣的擴散方式。
為什麼用它「先近後遠」讓爬蟲優先涵蓋離入口最近、通常也最重要的頁面，而且能設定最大深度就停。
看到這些關鍵字就想到它：最少步數、最短路徑（無權重）、幾層／幾度、離某點最近的、一圈一圈擴散。
02核心概念
BFS 從起點出發，先把距離 1 的節點全部看完，再看距離 2 的，像水波一圈一圈往外擴。之所以能做到「一圈一圈」，是因為它用 佇列（Queue） 記住待處理的節點：先被發現的先處理。
這個性質帶來 BFS 最重要的結論：在無權重的圖上，BFS 第一次碰到某個節點時，走過的邊數就是起點到它的最短距離。
03演算法步驟
- 1把起點放入佇列，並標記為「已發現」，避免之後重複加入。
- 2從佇列前端取出一個節點
u。 - 3看
u的每個鄰居v：若v尚未被發現，標記它，記下dist[v] = dist[u] + 1，然後放入佇列尾端。 - 4重複步驟 2–3，直到佇列為空。此時所有從起點可達的節點都已走訪。
04互動示範
從節點 A 開始。按「下一步」看佇列如何一層一層推進，節點下方的數字是與 A 的距離。
未發現在佇列中處理中已完成
佇列（前 → 後）
A
走訪順序
A
步驟 0/9把起點 A 放入佇列，dist[A] = 0。
05程式碼
from collections import deque
def bfs(adj, start):
# adj: dict[node, list[node]]，回傳每個節點到 start 的距離
dist = {start: 0}
queue = deque([start])
while queue:
u = queue.popleft() # 從前端取出
for v in adj[u]:
if v not in dist: # 尚未發現
dist[v] = dist[u] + 1
queue.append(v) # 放到尾端
return dist06練習題
- LeetCode 1091Shortest Path in Binary MatrixMedium
- LeetCode 994Rotting OrangesMedium
- LeetCode 127Word LadderMedium
- LeetCode 200Number of IslandsMedium
上一篇—下一篇DFS