以同心圓探索
在上一篇指南裡，你把一張圖以鄰接串列或鄰接矩陣的形式定在記憶體中，並看到：對稀疏圖而言，串列是最自然的歸宿，因為它讓你掃過一個頂點的鄰居時，花的時間正比於鄰居實際的數量。廣度優先搜尋（BFS）是建在那個表示法之上的第一個真正的演算法，它的構想簡單到近乎孩子氣：從一個來源頂點出發，拜訪它所有的鄰居，再拜訪那些鄰居尚未拜訪的鄰居，如此一圈圈往外漣漪。你以同心圓的方式探索整張圖——先是離來源一條邊的一切，再是兩條邊的一切，然後三條——在較近的圓圈徹底走完之前，絕不碰較遠的圓圈。
強制這種「一圈接一圈」順序的整個訣竅，就是單一一個資料結構：一個佇列，先進先出。你把來源放進佇列；然後反覆地從前端取出一個頂點，看它的每一個鄰居，對於每一個你從未見過的鄰居，把它標記為已拜訪、推進尾端。因為佇列以「被發現的順序」把頂點交還給你，而一個離兩條邊的頂點，永遠只在每個離一條邊的頂點都已入列之後才被發現，先進先出的紀律便悄悄保證：你會在第 2 圈開始前，徹底走完第 1 圈。不必排序、沒有優先權——只是一個樸素的佇列在記帳。這就是作為圖探索設計工具的 BFS：一趟可控的、走遍所有「從來源可達之物」的完整漫遊。
演算法，一步一步來
- 對來源 s 設 dist[s] = 0，對其他每個頂點設 dist[v] = 無窮大（意思是「尚未到達」）。把 s 放進佇列並標記為已拜訪。
- 當佇列非空時，把前端的頂點 u 出列。
- 對 u 的每一個鄰居 v（直接從 u 的鄰接串列讀出）：若 v 尚未拜訪，設 dist[v] = dist[u] + 1、記 u 為 v 的父節點、把 v 標記為已拜訪、並把 v 入列。
- 當佇列清空時，每個從 s 可達的頂點都在 dist[] 中帶著它正確的距離，而父節點指標為每一個頂點拼出一條回到 s 的最短路徑。
讓我們在一張小圖上跑跑看。頂點 a、b、c、d、e；邊有 a-b、a-c、b-d、c-d、d-e。從 a 出發。把 a 以 dist 0 入列。把 a 出列，看到 b 與 c：兩者皆新，所以 dist[b] = dist[c] = 1，兩者都入列。把 b 出列，看到 a（已拜訪，略過）與 d（新的），所以 dist[d] = 2，把 d 入列。把 c 出列，看到 a（略過）與 d（已經拜訪過了——略過！），沒有新的。把 d 出列，看到 e（新的），dist[e] = 3。把 e 出列，沒有新鄰居，佇列空了。最終距離：a=0、b=1、c=1、d=2、e=3——恰好就是每個頂點所在的那一圈。注意 d 是經由 b 到達的、而非 c，純粹因為 b 先從佇列出來；邊的數目是被迫定的，但具體的那條最短路徑，會取決於鄰居的順序。
這要花多少代價？每個頂點至多被入列一次（拜訪標記保證了這點），所以出列迴圈至多跑 |V| 次。而每次你把一個頂點出列，你會把它整條鄰接串列恰好掃一次，所以在整趟執行中，你看每條邊的次數是常數——無向圖裡兩次，每個方向各一次。把這些加起來得到 O(|V| + |E|)，與圖的大小成線性。這和一趟樸素遍歷的代價相同，也正是鄰接串列表示法為何如此要緊：在矩陣上，無論邊多麼少，每個頂點的鄰居掃描都要花 O(|V|)，把 BFS 拖到 O(|V|^2)。
為什麼那些層數真的就是距離
從追蹤中看到正確的距離跳出來是一回事；知道它們永遠正確又是另一回事。這個主張是精確的：當 BFS 結束時，對每個可達的 v，dist[v] 等於從 s 到 v 的最短邊數路徑——也就是從 s 到 v 任一路徑上的最少邊數。這個證明立足於一個關於佇列的整潔不變量，而它值得記在腦中，因為它正是 BFS 配得上「最短」二字的全部理由。
不變量是這樣的：在任何時刻，佇列裡至多只有兩個相異的距離值 d 與 d+1，且所有的 d 都坐在所有的 d+1 之前。換句話說，佇列永遠按距離排序、呈非遞減順序。為什麼先進先出能維持這點？當你把一個距離 d 的頂點 u 出列時，你入列的每個新鄰居都得到距離 d+1、並走到尾端——排在任何還在等待的 d 之後，並與已經在那裡的其他 d+1 整齊地對齊。所以你永遠不可能把一個頂點以亂掉的距離順序入列，你自始至終都以非遞減的距離處理頂點。這正是那種一圈接一圈的行為，只是現在被陳述成一個你能證明、而非僅能想像的東西。
由那個不變量，距離的主張可用歸納法推得。當 v 第一次被發現時，它是在展開某個 dist[u] = d 的 u 時被發現的，所以 dist[v] 被設為 d+1；又因為我們以非遞減的距離處理，沒有任何更晚、更長的路線能偷偷溜進來覆蓋它（反正拜訪標記也禁止第二次賦值）。一個簡短的論證可說明 d+1 確實是最小值：從 s 到 v 的任一路徑，在 v 之前都有一個最後的頂點，那個頂點在它自己的最短路徑上距離至少為 d，所以 v 不可能比 d+1 更近。誠實的提醒：這套乾淨的推理，仰賴每條邊都恰好算作一步。一旦邊帶著不同的權重，佇列不變量就破了——一條便宜的兩邊路線可能勝過一條昂貴的一邊路線——而 BFS 純粹就是用錯了工具，下一節會把這點講得鋒利。
承諾停止之處：權重
BFS 解決單源最短路徑問題，但只解決它無權重的版本——也就是「最短」意指最少邊數的版本。一旦你的邊有了長度或成本，最少邊數與最小總成本就可能彼此不合，而 BFS 會樂呵呵地回傳最少邊數的答案，那可能離最便宜差得很遠。想像 s 用兩種方式連到 t：一條權重 10 的直接邊，和一條繞道兩跳 s-x-t、權重各為 1 與 1 的路。BFS 宣布直接邊勝出（一條邊勝過兩條）、回報成本 10，而真正最便宜的路徑成本是 2。BFS 在這裡並沒有壞——它回答了它真正解決的那個問題，而那對一張帶權圖來說是錯的問題。
修法不是去補 BFS，而是升級那個佇列。如果你把樸素的先進先出佇列換成一個優先佇列，讓它總是交還暫定距離最小的頂點，你就得到了戴克斯特拉演算法——BFS 帶權重的大哥哥。BFS 以發現順序取出頂點，戴克斯特拉則以「已知最便宜成本」的順序取出，這正是當各圈圈厚薄不一時，「最近的圈圈優先」正確的推廣。而這裡住著整個最短路徑領域裡最重要的誠實提醒之一：戴克斯特拉只有在每條邊權重皆非負時才正確。單一一條負邊，就可能讓一個頂點真正最便宜的成本，在戴克斯特拉已經把它定案之後才下降，把演算法弄壞；對帶有負邊的圖，你需要另一個方法（貝爾曼-福特），代價更高。
BFS 順手送你的兩樣東西
BFS 沿途記下的父節點指標，會編織成一棵以來源為根的BFS 樹：一棵涵蓋所有可達之物的生成樹，其中從根到任一頂點 v 的唯一樹上路徑，就是一條到 v 的、貨真價實的最短（最少邊數）路徑。這是免費的紅利——你想要的是距離，而你也順帶得到了到每個頂點的明確最短路徑，只要從 v 沿父節點連結倒走回 s 就能重建。若這張圖有好幾塊互不相連的部分，一趟 BFS 只能抵達來源那一塊；從任何仍未拜訪的頂點重啟 BFS、反覆進行，直到沒有剩下的為止，而重啟的次數恰好就是連通分量的數目。每次重啟的樹，就是那個分量自己的 BFS 樹。
第二份禮物是二分圖檢測。一張圖是二分的，如果你能把它的頂點二著色，使得每條邊都連接不同顏色——等價地說，如果它沒有奇數長度的環。BFS 幾乎免費地檢測這點：用每個頂點 BFS 層數的奇偶性來著色，來源第 0 層一種顏色、所有奇數層另一種、所有偶數層回到第一種。然後做一個檢查——有沒有任何一條邊連接兩個層數奇偶性相同的頂點？若沒有任何邊如此，著色有效、這張圖是二分的。若某條邊連接兩個同色頂點，那條邊加上通往它們共同祖先的樹上路徑，就閉合出一個奇環，而奇環永遠無法被二著色，所以這張圖可證明不是二分的——你甚至能把那個違規的奇環當作見證交還回去。
這兩樣都搭在同一趟 O(|V| + |E|) 的掃描之內——沒有額外的漸進成本，只是把一個奇偶欄位和一個顏色檢查，摺進既有的迴圈裡。這就是本篇指南安靜的教訓：BFS 與其說是單一一個演算法，不如說是一副可重用的底盤。下一篇指南把佇列換成堆疊（明確地、或透過遞迴），得到深度優先搜尋，它拿 BFS 的距離保證，去換一種不同的超能力——把邊豐富地分類為樹邊、回邊、前向邊與交叉邊，從而解鎖環的偵測、拓樸排序，以及這一階其餘的大半內容。