圖搜尋有兩個不同問題:哪些頂點可到達?到達它們最少要經過多少條邊?在無權圖中,廣度優先搜尋(BFS)可同時回答兩者。隊列讓較早的距離層先處理,父指標則記錄一條證明答案的路徑。
一個小操作的時機很重要。若頂點只在離開隊列時才標記,多個鄰居可能早已把它重複入隊。改為在入隊時標記,可令每個頂點最多入隊一次,也固定首次發現它的父頂點。我們會證明第一次發現已經給出最短路徑,而不只相信一個例子。
定義距離和數據結構
定義 13.1.1
(最短路徑距離)
令 為有限有向圖,頂點為 ,其中 ;選定起點 。每條列出的有向邊算一步。若存在從 到 的有向路徑,距離 是其最少邊數;否則設 。起點透過零長路徑到達自身,距離為零。
無向邊可在兩個方向各存一個鄰接項。允許自環及重複鄰接項,但它們不會造出更短路徑。以下用 計算列出的有向鄰接項數,重複項也計算在內。
定義 13.1.2
(隊列和標籤)
維持先入先出隊列、距離陣列與父頂點陣列。距離的 None 表示尚未發現。起初起點距離為 0 並已入隊;其他距離及所有父頂點均為 None。
移除頂點 時,檢查它列出的每個出鄰居 。若 distance[v] 是 None,便設為 distance[u] + 1,設 parent[v] = u,並立即把 加入隊列。若 已被發現,保持其標籤與父頂點不變。距離陣列同時充當發現標記。
算法結束後,距離陣列中的 None 表示不可到達;執行期間它只表示尚未發現,之後的隊列項仍可能到達該頂點。
常見錯誤
(太早把 None 當作不可到達)
在六頂點例子中移除 1 之後,distance[4] 仍是 None,但 4 可由 0 到達。搜尋進行期間,None 只表示尚無已移除的頂點發現過它;只有隊列清空之後,它才表示不可到達。
追蹤兩條可能路徑
例題 13.1.3
(隊列逐層顯示距離)
以下鄰接表按列出次序讀取,起點為 0:
| 頂點 | 出鄰居 |
|---|---|
| 0 | 1, 2 |
| 1 | 3 |
| 2 | 3, 4 |
| 3 | 4 |
| 4 | 無 |
| 5 | 無 |
隊列起初是 [0]。移除 0,發現 1 和 2,得到 [1, 2]。移除 1,發現 3,得到 [2, 3]。移除 2,先看到 3 已被發現,再發現 4,得到 [3, 4]。餘下的移除沒有新增頂點。
最後距離為 [0, 1, 1, 2, 2, None]。一組父頂點是 [None, 0, 0, 1, 2, None]:由 4 沿父指標得到 4、2、0,倒轉後是最短路徑 。路線 也是有向路徑,但用了三條邊。起點 0 無法到達頂點 5。
若 0 的鄰接表改成 [2, 1],頂點 3 可能改以 2 為父頂點。BFS 可以選到不同的最短路徑見證,但距離不會因此改變。
例題 13.1.4
(自環與重複項只影響 m)
取鄰接表 0: [1, 1, 0]、1: [2, 0]、2: [1],起點為 0。移除 0 時發現 1,距離 1、父頂點 0;重複的 1 和自環 0 都碰到已有標籤的頂點,不產生任何改變。移除 1 時發現 2,距離 2、父頂點 1,項 0 被跳過。移除 2 時檢查 1,它已有標籤。結果是距離 [0, 1, 2]、父頂點 [None, 0, 1]。共檢查了六個鄰接項,所以 ,但每個頂點只入隊一次。
為何第一次發現已經最短
定理 13.1.5
(BFS 計算最短距離)
設 為有限有向圖, 為其中一個頂點。隊列清空後,對每個可從 到達的頂點 ,distance[v] 等於 ;不可到達的頂點,distance[v] 恰好是 None;而從可到達的 沿父指標回溯,得到一條從 出發、長度恰為該距離的路徑。
證明
(先入先出維持非遞減距離層)
起點以標籤 0 入隊。每當移除標籤為 的頂點,所有新入隊鄰居的標籤都是 。隊列中的標籤非遞減:起初只有一個零;移除隊首不破壞次序,而新標籤不小於隊中現有標籤。更精確地,處理第 層時,隊列只含尚未處理的 ,其後可能接著 。移除一個 並在尾部加入 後,性質仍然成立。
每個已發現頂點都確實有一條長度等於其標籤的起點路徑:起點使用空路徑;每次發現只在父頂點的見證路徑後加一條邊。因此標籤不可能小於真正的最短距離。
反過來,設可到達頂點 的最短距離是 ,選一條最短路徑 。對 歸納。起點的標籤是零。若 的標籤至多 ,它最終會被移除:頂點有限,每個頂點最多入隊一次。移除時, 要麼已有標籤,要麼藉邊 得到至多 的標籤。
若它更早已有標籤,先入先出的層次次序說明,發現它的頂點的標籤不大於移除 時的標籤。因此它的標籤也至多 。故 的標籤至多 ;結合已有實際路徑的反向不等式,標籤恰等於 。
隊列清空後,上述論證說明每個可到達頂點都已被發現;不可到達頂點不可能被發現,因為每次發現都附有從起點出發的實際路徑。因此餘下的 None 恰好是不可到達的頂點。
證明透視
先入先出用在哪一步
整個證明只有一步需要隊列的規則: 在 被移除之前已有標籤的情況。那時發現它的頂點更早被移除,而先入先出使移除時的標籤非遞減,所以該頂點的標籤至多等於 的標籤, 因而得到至多 的標籤。其餘部分,即見證路徑和有限終止,與次序無關。若以堆疊取代隊列,正是這一步失效,見下面的例子。
也可用移除次序作較短的證明:若新發現的頂點另有嚴格更短路徑,該路徑上緊接它之前的頂點應在較早一層先被移除,從而更早發現它。兩種證明都依賴 FIFO 次序,而不只依賴最終有否遍訪頂點。
反例模式
用堆疊並在發現時標記,距離會出錯
取有向邊 、、、、,鄰接表按此次序,起點為 0,並把隊列換成堆疊,仍然在推入時標記頂點。移除 0 時推入標籤同為 1 的 1 和 2;位於堆疊頂端的 2 最先被移除,並推入標籤為 2 的 3;移除 3 時推入標籤為 3 的 4。頂點 1 最後才被移除,發現 4 已有標籤。算法報告頂點 4 的距離是 3,但路徑 的長度只有 2。每個頂點仍然只被發現一次,可見「發現時標記」本身不足以給出最短路徑,真正起作用的是先入先出的次序。
邊界清楚的實作
輸入是可按索引讀取的鄰接序列,每個鄰居都是整數頂點。以下版本檢查所有鄰居索引,包括起點無法到達的分量,且不修改輸入。使用 deque 可從隊首移除而不必搬移整個陣列。
from collections import deque
def breadth_first_search(graph, source):
n = len(graph)
if not 0 <= source < n:
raise ValueError("source outside the vertex range")
for neighbors in graph:
for vertex in neighbors:
if not 0 <= vertex < n:
raise ValueError("neighbor outside the vertex range")
distance = [None] * n
parent = [None] * n
distance[source] = 0
queue = deque([source])
while queue:
u = queue.popleft()
for v in graph[u]:
if distance[v] is None:
distance[v] = distance[u] + 1
parent[v] = u
queue.append(v)
return distance, parent
def shortest_path(distance, parent, source, target):
if not 0 <= source < len(distance) or not 0 <= target < len(distance):
raise ValueError("endpoint outside the vertex range")
if distance[target] is None:
return None
path = []
v = target
while v != source:
path.append(v)
v = parent[v]
path.append(source)
path.reverse()
return path
shortest_path 假設收到的是同一起點執行 breadth_first_search 返回的陣列。目標就是起點時返回 [source]:零邊路徑不需要父頂點。不可到達的目標返回 None。對已發現的非起點頂點,每個父頂點的距離恰好少一,所以回溯有限步後到達起點。倒轉收集的頂點,便得長度恰好等於標籤的正向路徑。
概念視角結構
輸出是一棵分層的樹
設 為各距離層。從可到達頂點 出發的每條有向邊 都滿足 ,所以它或者留在同一層,或者退回較早的層,或者恰好前進一層。父指標對應的邊就是用來發現頂點的前進邊:每個可到達的非起點頂點恰有一條,它們構成以 為根的樹,邊數為各層頂點總數減一。在六頂點例子中,各層為 ,樹邊為 、、、;邊 留在第 2 層之內。
例題 13.1.6
(重建路徑,包括起點本身)
沿用六頂點例子的陣列:距離 [0, 1, 1, 2, 2, None],父頂點 [None, 0, 0, 1, 2, None]。目標為 3 時,迴圈收集 3 與 1,再加入起點 0,倒轉後得到 [0, 1, 3],共兩條邊,等於 distance[3]。目標為 0 時,迴圈體一次也不執行,結果是 [0]。目標為 5 時距離為 None,函數返回 None。只有一個頂點而沒有邊的圖 graph = [[]],搜尋返回距離 [0] 與父頂點 [None]。
輸入契約假設頂點為整數、鄰接序列格式正確;邊界檢查不會驗證所有可能格式錯誤的 Python 物件。產品介面可按自身契約增加較嚴格的類型與錯誤處理。
計算工作量,也避免誤用於加權圖
命題 13.1.7
(BFS 的時間與空間)
以上述實作,搜尋需 時間及 個額外單元,其中 計算列出的有向鄰接項數,重複項也計算在內。重建含 條邊的路徑需 時間。
證明
(頂點數與鄰接項數)
初始化及驗證掃描需 時間。每個頂點最多入隊及移除一次,每個已到達頂點的出鄰接項最多檢查一次,額外時間至多 。距離、父頂點與隊列使用 額外空間,不包括輸入圖。重建含 條邊的路徑需 時間及輸出空間。
反例模式
邊數最少未必權重最小
假設加權有向圖有 、權重 10,另有 與 ,各權重 1。BFS 把每條邊當作一步,選擇只有一條邊的直接路徑,權重卻是 10;兩條邊的路徑總權重是 2。上述 BFS 證明優化的是邊數,不是任意權重總和;即使允許零權重邊,一般 BFS 也不是通用加權最短路徑算法。
BFS 是一種搜尋次序,不能代替目標的定義。若邊權重要,應選擇符合其假設的算法並證明相應不變量。對無權問題,隊列次序及首次發現的父頂點共同提供最佳距離與可檢查的見證。
練習與解答
快速檢查
(1. 在六頂點例子,移除 1 後隊列是甚麼?給出到 4 的一條最短路徑。)
解答 · 解答 1
移除 1 後隊列是 [2, 3]。其後 2 發現 4,沿父頂點得到最短路徑 ,長度為 2。在 2 被移除之前 4 尚未發現;當時的 None 不代表它不可到達。
快速檢查
(2. 起點自身的距離與路徑是甚麼?例子中的頂點 5 又返回甚麼?)
解答 · 解答 2
起點距離為 0,路徑是 [0],即零長路徑。頂點 5 的距離為 None,搜尋完成後可知起點無法到達它,因此 shortest_path 返回 None。
快速檢查
(3. 若 、、、,為何只在移除 3 時標記可能產生額外隊列項?)
解答 · 解答 3
3 到達隊首之前,1 和 2 均可能先檢查它。若入隊時沒有記錄發現,兩者都可能把它入隊。第一次由 1 入隊時立即標記,便令 2 之後看到它已發現而跳過,只保留一個隊列項與一個首次父頂點。不同鄰接次序仍可選到另一個同樣短的父頂點。
快速檢查
(4. 為何搜尋是 而不是 ?此處 m 計算甚麼?)
解答 · 解答 4
陣列只初始化一次,每個頂點最多入隊一次。掃描被移除頂點的鄰接表時,每個列出的出鄰接項最多檢查一次;事前驗證亦只掃描一次,故總工作是 。 包括重複的有向鄰接項;若無向邊兩方向各存一次,便貢獻兩項。