廣度優先搜尋按距離層探索圖;深度優先搜尋(DFS)則沿一條路徑走到盡頭才回頭。這種次序對最短路徑用處不大,卻能揭示圖的結構:環、子孫關係,以及工作的合法先後次序。分析之前必須先決定圖如何儲存,因為所有圖算法的成本都取決於這個選擇。前面的廣度優先搜尋單元已預設使用鄰接表,本單元說明這個選擇的理由。
表示法
設 為有限有向圖,有 個頂點 及 條弧。無向邊以兩條弧儲存。
定義 13.2.1
(鄰接矩陣與鄰接表)
鄰接矩陣是 陣列 :若存在弧 則 ,否則為 。鄰接表為每個頂點 儲存一個列表,列出所有滿足弧 的頂點 。
| 操作 | 矩陣 | 鄰接表 |
|---|---|---|
| 空間 | ||
| 是否為弧? | ||
| 列出 的所有出鄰居 | ||
| 遍歷每條弧一次 |
其中 是離開 的弧數。若 ,圖稱為稀疏(路線圖、依賴關係圖多屬此類);若 則稱為稠密。稀疏圖用鄰接表佔用空間小得多,遍歷也快得多;稠密圖兩者空間同階,而矩陣可在常數時間內查詢弧。遍歷需要逐個掃描每個頂點的鄰居,所以 DFS 與 BFS 預設使用鄰接表。
算法
DFS 為每個頂點記錄顏色:白色(未發現)、灰色(已發現但未完成,即正在遞歸堆疊上)、黑色(已完成)。全域時鐘記錄兩個時間戳:發現時間 與完成時間 。
def dfs_all(graph):
n = len(graph)
color = [0] * n # 0 white, 1 gray, 2 black
d = [0] * n
f = [0] * n
clock = 0
finish_order = []
back_edges = []
def visit(u):
nonlocal clock
color[u] = 1
clock += 1
d[u] = clock
for v in graph[u]:
if color[v] == 0:
visit(v)
elif color[v] == 1:
back_edges.append((u, v))
color[u] = 2
clock += 1
f[u] = clock
finish_order.append(u)
for s in range(n):
if color[s] == 0:
visit(s)
return d, f, finish_order, back_edges
外層迴圈從每個白色頂點重新開始,整個圖因而都被覆蓋,得到一片由 DFS 樹組成的森林。每個頂點只被造訪一次,因為它在檢查鄰居之前已經着色;每條弧只被檢查一次,即展開其起點時。使用鄰接表時,執行時間為 ;使用矩陣則為 。遞歸深度可達 ,所以遞歸上限較小的語言處理長路徑時需要顯式堆疊。
概念視角結構
灰色頂點構成當前路徑
任何時刻,灰色頂點恰好就是由當前 DFS 樹的根走到正被展開的頂點的那條樹路徑上的頂點,按發現次序排列。每次調用 visit 把該頂點加入這條路徑,頂點變為黑色時才移出。因此黑色頂點構成已完成的子樹,白色頂點則尚未接觸。這是對同一個搜尋的另一種讀法:指向灰色頂點的弧沿當前路徑往回指,指向黑色頂點的弧則指向已經完成的部分。
搜尋的結構
定理 13.2.2
(括號性質)
對任意兩個頂點 ,區間 與 要麼不相交,要麼其中一個包含另一個。頂點 是 在 DFS 樹中的子孫,當且僅當 。
證明
(調用像堆疊一樣巢狀)
所有時間戳都互不相同,所以對 可設 。若 ,則 在 仍為灰色時被發現,即發生在調用 visit(u) 期間。調用像堆疊一樣巢狀進行,所以 visit(v) 先於 visit(u) 返回,即 。若 ,兩區間不相交。關於子孫的敘述: 的子孫都在 visit(u) 期間被發現,因此區間互相巢狀;反過來,若 ,則 在 visit(u) 期間被發現,所以它屬於由 開始的調用所形成的子樹。 與 對調的情形對稱。
檢查弧 時,由 的顏色和時間戳判斷其類型:
- 樹弧: 為白色(它成為 的子節點);
- 回邊: 為灰色( 是 的祖先,也可能就是 本身);
- 前向弧: 為黑色且 ( 是 的非子節點的子孫);
- 橫跨弧: 為黑色且 (沒有祖孫關係; 在 開始前已完成)。
定理 13.2.3
(環與回邊)
有限有向圖含有有向環,當且僅當對它作深度優先搜尋時找到回邊。
證明
(回邊給出環,環必產生回邊)
若有回邊 ,則 為灰色,所以 是 的祖先(或 ),從 到 的樹路徑加上弧 便是一個環。
反之,設 為一個環, 為 上發現時間最小的頂點。把 寫成 ,其中 ( 即 上的自環)。 被發現時, 全是白色。對 作歸納,證明每個 都在 visit(w) 期間被發現。 顯然成立。設結論對 成立。調用 visit() 位於 visit(w) 之內,並在返回之前檢查弧 。若此刻 是白色,它成為 的子節點;否則它已在 之後被發現(因為當時它是白色),所以是在 visit(w) 期間被發現。兩種情形下 都在 visit(w) 期間被發現。
特別地, 是 或 的子孫,並在 visit(w) 之內檢查弧 。此時 尚未完成,仍是灰色,所以弧 是回邊。
證明透視
為甚麼要取最先被發現的頂點
逆向的證明取決於一個選擇: 是 上最先被發現的頂點。這個選擇有兩個作用:使 的其餘頂點在時間 都是白色,歸納由此開始;也保證通往 的閉合弧是在 仍未完成時被檢查,所以 是灰色。環上其他頂點都不行。例如 、 從 0 開始搜尋, 雖在環上,卻在 0 之後才被發現,所以在時間 ,頂點 0 是灰色而不是白色,白色路徑的論證無從開始。此時回邊是 ,它指向最先被發現的頂點。自環的情形 不需另行論證:,檢查 自己的弧時 是灰色。
定理 13.2.4
(由完成時間得拓撲次序)
若有向圖無環,則把頂點按完成時間由大到小列出,便得到拓撲次序:對每條弧 , 都排在 之前。
證明
(每條弧的終點先完成)
考慮在 visit(u) 期間檢查的弧 。 不可能是灰色,否則它是回邊,圖便有環。若 為白色,它成為 的子孫並先完成,故 。若 為黑色,它已完成,同樣 。兩種情形下 都先於 完成,所以在完成時間遞減的次序中 在前。
反例模式
發現次序不是拓撲次序
有人會想按發現時間由小到大列出無環圖的頂點。取 、、,先從 0 再從 2 搜尋,得 、,發現次序為 。弧 在其中指向後方,因為 2 比 1 遲發現。按完成時間由大到小則得 ,弧 與 都指向前方。較晚開始的頂點仍可排在較早的前面,所以只有完成時間才有保證。
例題
例題 13.2.5
(六個頂點的有向無環圖上的 DFS)
鄰接表為 、、、、、。從 0 出發,時鐘為 0。造訪 0(),然後 1()、3()、5()。5 沒有鄰居,所以 。回到 3,;回到 1,。返回 0,檢查 2:。它的第一個鄰居 3 是黑色且 ,所以 是橫跨弧。第二個鄰居 4 是白色:;4 的鄰居 5 是黑色且發現時間較小,是橫跨弧;,,。
完成次序為 ,按完成時間遞減得 。逐條弧檢查:、、、、、、 全部由此列表中較前的頂點指向較後的頂點。樹弧為 、、、、。
例題 13.2.6
(以回邊找出環)
取 、、、。DFS 依次發現 ,。在頂點 2,第一個鄰居是 0,它是灰色,所以 是回邊。堆疊上的灰色頂點為 ,沿堆疊從 0 走到 2,再加上回邊,得到環 。搜尋繼續:3 是白色,,;然後 ,,。
再加入前向弧:若圖中還有弧 ,列在 之後,則 0 在完成 1 之後繼續時,頂點 2 是黑色,且 ,所以 是前向弧。
例題 13.2.7
(自環與多棵搜尋樹)
取 、、。外層迴圈從 開始。頂點 0 變為灰色,,它唯一的鄰居就是 0 本身,而 0 是灰色,所以 是回邊,圖含有長度為一的環。然後 。頂點 1 仍是白色,外層迴圈便開始第二棵樹:,白色鄰居 2 得 、,再 。結果是兩棵樹(根分別為 0 和 1)組成的森林,另有一條回邊。
兩個邊界情形都在此出現。自環是顏色判斷不需特別處理就能偵測的環,因為檢查 自己的弧時 是灰色。此外,若只從一個起點搜尋,便會漏掉頂點 1 和 2,這正是外層迴圈屬於算法一部分的原因。
常見錯誤
反例模式
無向圖:父節點不構成環
把含邊 、 的無向路徑以雙向弧儲存,並使用「灰色鄰居即有環」的判斷。在頂點 1,鄰居 0 是灰色,因為它是我們到達 1 時所經的父節點,於是判斷錯誤地報告有環。在無向簡單圖中,應跳過一次通往樹父節點的弧;此後任何其他灰色鄰居才表示有環。若有平行邊,通往父節點的第二條邊確實構成環,所以應按邊的身分而非按頂點來跳過父邊。
常見錯誤
(把完成次序順著讀)
取單一條弧 。從 0 搜尋得 、、、,完成次序是 ,弧在其中指向後方。拓撲次序是它的反轉,即 。若圖有環,則根本不存在拓撲次序,所以須先檢查定理的前提,例如找找有沒有回邊。
常見錯誤
(頂點到完成時才標記)
頂點必須在進入時着色,而不是在完成時。對 、,若 0 到結束才被標記,則 visit(1) 會把 0 視為白色,再次調用 visit(0),遞歸永不停止。進入時着色才有灰色狀態,回邊偵測也才可能。
習題與解答
快速檢查
(有向圖有 n = 1000 個頂點、m = 3000 條弧。比較矩陣與鄰接表儲存的項數,以及在兩者上作 DFS 的成本。)
解答 · 答案
矩陣儲存 項;鄰接表儲存 個表頭加 個弧項,約 個單元。在鄰接表上 DFS 需 步;在矩陣上,1000 個頂點各掃描一行 1000 項,需 步。此圖稀疏,所以鄰接表較優。
快速檢查
(對 0:[2]、1:[0]、2:[1,3]、3:[ ] 從 0 出發作 DFS。求 d、f、各弧類型及環。)
解答 · 答案
造訪 0(),然後 2(),再 1()。弧 發現 0 為灰色:回邊。。回到 2,頂點 3 是白色:,。然後 ,。弧的類型:、、 是樹弧, 是回邊。環為 。所有頂點均已完成,外層迴圈不會再從別處開始。
快速檢查
(區間:A=[1,8]、B=[2,5]、C=[3,4]、D=[6,7]。分類弧 A 到 C、C 到 A、D 到 B、A 到 D。)
解答 · 答案
從區間可見 在 內, 在 內, 在 內但與 不相交。弧 : 是 的子孫但不是子節點(它在 內),檢查時它是黑色且 :前向弧。弧 : 是祖先,為灰色:回邊。弧 : 在 開始前已完成(),為黑色且 :橫跨弧。弧 : 與 之間沒有別的頂點包含 ,所以 是 的子節點:樹弧。
快速檢查
(以完成時間為 0:[3]、1:[3,4]、2:[4]、3:[ ]、4:[ ] 求一個拓撲次序,DFS 依 0、1、2 的次序開始。)
解答 · 答案
從 0:,造訪 3:,,然後 。從 1:;3 為黑色;造訪 4:,;。從 2:;4 為黑色;。完成次序為 ,反轉得 。每條弧都向前:(位置 4 與 5)、(2 與 5)、(2 與 3)、(1 與 3)。
快速檢查
(無向圖有邊 {0,1} 與 {1,2}。為何「灰色鄰居即有環」會誤報,如何修正?)
解答 · 答案
每條無向邊以兩個方向儲存。DFS 由 0 到達 1 時,鄰居 0 是灰色,因為它是樹父節點,而不是因為有環。修正方法是忽略那條經由發現當前頂點時所用的邊、通往父節點的弧。只有經由另一條邊到達的灰色鄰居,才表示有環。