在有向圖中,能從一個頂點走到另一個,不代表能夠返回。依賴圖可以包含內部互通的群組,群組之間卻只有單向連接。要推理這些群組的先後關係,須先精確找出哪些頂點可以互相到達。
強連通分量把兩種結構分開。在同一分量內,每個頂點都可到達其他每個頂點;把各分量收縮之後,分量之間則不再有有向環。所得圖是有向無環圖,所以看似帶環的依賴系統,可以視為內部帶環群組的無環排列。
我們將推導通常稱為 Kosaraju 算法的兩遍 DFS 方法。第一遍探索原圖,記錄的是完成次序;第二遍探索全部邊倒轉後的圖,並使用該次序的反向。正確性依賴這些精確選擇,不是任意做兩次可達搜尋就足夠。
互相可達定義分量
設 為有限有向圖,頂點為 ,容許 ,也容許平行弧及自環。若存在從 到 的有向路徑,寫成 ;當 ,包括長度為零的路徑。
定義 10.2.1
(強連通是一個等價關係)
定義
強連通分量,簡稱 SCC,是這個關係的一個等價類。等價地,它是互相可達頂點的極大集合。孤立頂點也構成單點分量,不需要自環。
零長度路徑使關係具有自反性;定義本身給出對稱性。若 且 ,串接路徑便同時得到 及 ,證明傳遞性。因此分量劃分全部頂點,而不會彼此重疊。
同一分量內頂點之間的連接路徑,可以完全位於該分量內。若 在一條由 到 的路徑上,而且 ,則有 ,所以 。每個中途頂點也屬於同一分量。
轉置圖 把每條 換成 。路徑倒轉後,可達關係的方向也倒轉,所以互相可達的關係不變,SCC 劃分亦不變。
收縮分量後不會剩下有向環
定義 10.2.2
(凝聚圖)
凝聚圖每個頂點代表一個 SCC;當 ,而且原圖有邊從 的頂點指向 的頂點,就加入弧 。分量內的邊省略,同一對分量之間的平行弧只需保留一份。
定理 10.2.3
(凝聚圖無環)
有限有向圖的凝聚圖是有向無環圖。
證明
(分量的環會使它們合併)
假如不同的分量頂點形成有向環,利用各分量內的強連通性,就能沿環在任意兩個分量之間雙向到達。它們其實會屬於同一等價類,與彼此不同矛盾。因此凝聚圖是 DAG。
這並沒有說原圖無環,而是說所有有向環都位於各自的強連通分量內。凝聚圖保留的是分量之間的單向關係。
第一遍 DFS 記錄返回,而非發現
在 上執行普通有向 DFS 森林,每個尚未到訪頂點都可開啟一棵新 DFS 樹。當頂點的所有出弧都檢查完,而且遞歸發現的後代都已返回,才給它完成時間。只需在此事件把頂點加到串列尾端;位置越後表示完成時間越晚。
對分量 ,令 為其中頂點的最大完成時間。不同分量的個別頂點,不一定各自連續地完成。我們所需的敘述,是關於分量最大值:
定理 10.2.4
(完成時間最大值沿凝聚圖的弧遞減)
設 為強連通分量。若凝聚圖有弧 ,則
證明透視
跨分量邊決定最大完成時間的次序
考慮 與 並集中,最先被發現的頂點屬於哪一塊。
若該頂點在 ,其 DFS 可走遍 ,沿跨分量邊到 ,再走遍 。分量內路徑已足以支持這個論證。這些當時尚未發現的頂點,都會在首個 頂點完成前探索完畢。該頂點具有 內最大完成時間,並晚於 的每個頂點完成,所以 。
若最先發現的頂點在 ,就不可能有從 到 的路徑,即使經過其他分量也不可能,否則配合 會令兩分量互相可達。由該首個頂點開始的 DFS,會在發現任何 頂點之前,先走遍並完成 。所以 的全部完成時間,都早於 內的某個完成時間,同樣得到 。
引理比「某次 DFS 剛好先看見某群組」更強:它以完成最大值,指出每條跨分量依賴的方向。
常見錯誤
(比較個別完成時間而不是分量最大值)
取弧 、、,鄰點按遞增次序嘗試。分量為 與 ,完成次序為 。弧 離開第一個分量,但該分量中的頂點 1 比頂點 2 先完成。只有最大值的比較是正確的: 的最大完成名次是 , 的是 。
第二遍搜尋無法逃離選中的分量
按完成時間遞減掃描頂點。每當下一個頂點尚未獲分配,就從它在 上開始可達搜尋,而且只走未分配頂點。把本次新到達的全部頂點分配到同一分量。這一遍只需要堆疊或佇列,不必再計算完成次序。
定理 10.2.5
(兩遍算法的正確性)
對 執行 DFS 並記錄完成次序。然後按完成次序遞減掃描頂點;在每個未分配的頂點,只經過未分配頂點在 中搜尋,並給到達的全部頂點一個新編號。這些搜尋恰好分配出 的強連通分量,而且不同分量之間的每條弧 都滿足 component[u] < component[v]。
證明透視
選中分量在轉置前是源點,轉置後是匯點
以歸納假設先前每次選中的分量,都已完整分配。因此剩下的分量全部尚未分配。完成時間遞減序列中的首個未分配頂點,屬於剩餘分量中 最大的一個 。
不可能有原圖邊從另一剩餘分量 指入 ,否則引理要求 。轉置後,便沒有邊由 指向不同的未分配分量。略過已分配頂點時,搜尋無法離開 。
另一方面, 的全部頂點仍可在 中,沿完全位於 內的路徑從選中頂點到達。因此搜尋會找齊它們,恰好分配整個 ,完成歸納步驟。重複至沒有剩餘頂點,就得到精確 SCC 劃分。
按這個兩遍方向,分量依原凝聚圖中由源點向匯點的拓撲次序產生。若依次編號為 0、1、2 等,每條跨分量原圖邊 都滿足 component[u] < component[v]。這個次序解讀依賴先用 、再用 ;不要交換兩遍後,仍預設相同編號方向。
反例模式
單獨一條弧已能揭示發現次序及未轉置的錯誤
只取邊 。由 0 開始 DFS,發現次序是 ,完成次序卻是 。若倒轉發現次序,第二遍會在轉置圖由 1 開始;轉置圖有 ,便錯誤合併兩頂點。
正確反向完成次序是 。但若用它搜尋原圖而非轉置圖,首個由 0 開始的搜尋又會到達兩頂點,仍然錯誤合併。真正分量是 及 ,因為原圖中 1 無法到達 0。
完整追蹤,包括孤立分量
例題 10.2.6
(孤立頂點可排在一串相連分量之前)
使用以下鄰接串列,鄰居依所寫次序檢查,外層根頂點則按編號遞增考慮:
| 頂點 | 出邊鄰居 |
|---|---|
| 0 | 1 |
| 1 | 2, 3 |
| 2 | 0, 3 |
| 3 | 4 |
| 4 | 3, 5 |
| 5 | 6 |
| 6 | 5 |
| 7 | 無 |
第一棵由 0 開始的 DFS,依次發現 1、2、3、4、5、6;返回時把 加入串列。之後頂點 7 提供最後一項,因此完整完成串列是 。
第二遍依 考慮根,依次分配 、、、。所以編號陣列為 。第一個非單點分量有兩條邊連到下一分量,凝聚後只保留一條邊。邊集是 ,而分量 0 仍是孤立 DAG 頂點。
完成事件由 1 起計時,各最大值為: 是 7, 是 4, 是 2, 是 8。它們沿每條凝聚邊遞減;互不相關的分量不需要特定相對次序。
例題 10.2.7
(帶尾巴的有向環)
取 及弧 、、、。從 0 出發的 DFS 依次走 ,然後在 2 處,通向 0 的弧遇到已被發現的頂點,通向 3 的弧發現 3。返回事件依次追加 。轉置圖的弧為 、、、。第二遍依 考慮根。從 0 出發先到達 2,再到達 1,把 分配為編號 0。下一個未分配的根是 3;它在轉置圖中唯一的弧指向已分配的頂點 2,搜尋就此停止,把 分配為編號 1。編號陣列為 ,跨分量的弧 滿足 。凝聚圖有一條邊 。
用明確框架保留 DFS 返回事件
普通可達搜尋使用的頂點堆疊,不一定重現遞歸 DFS 的完成事件。第一遍中,每個框架須記住下一條要檢查的出弧。該框架耗盡鄰接串列時,才把頂點加到完成串列並彈出。下降到新子頂點之前,先推進父框架的索引,返回後便可從下一條弧繼續。
頂點應在推入時標記,不是等彈出才標記。這樣重複弧、有向環及自環,都不會把同一未發現頂點推入多次。第二遍只需可達性,所以堆疊可以只存頂點,不存返回索引。
下列輸入是可按索引存取的鄰接序列,各鄰接項也是序列,鄰居標籤為整數。非法鄰居索引會被拒絕,包括 Python 原本會解讀成從尾部索引的負數。程式只讀輸入而不修改。函數傳回每頂點的分量編號,以及每分量的成員串列;成員次序和互不相關分量的相對編號並不唯一。
def strongly_connected_components(graph):
n = len(graph)
transpose = [[] for _ in range(n)]
for vertex, neighbors in enumerate(graph):
for neighbor in neighbors:
if not 0 <= neighbor < n:
raise ValueError("neighbor outside the vertex range")
transpose[neighbor].append(vertex)
seen = [False] * n
finish = []
for root in range(n):
if seen[root]:
continue
seen[root] = True
stack = [(root, 0)]
while stack:
vertex, index = stack[-1]
if index == len(graph[vertex]):
stack.pop()
finish.append(vertex)
continue
neighbor = graph[vertex][index]
stack[-1] = (vertex, index + 1)
if not seen[neighbor]:
seen[neighbor] = True
stack.append((neighbor, 0))
component = [-1] * n
groups = []
for root in reversed(finish):
if component[root] != -1:
continue
identifier = len(groups)
component[root] = identifier
stack = [root]
members = []
while stack:
vertex = stack.pop()
members.append(vertex)
for neighbor in transpose[vertex]:
if component[neighbor] == -1:
component[neighbor] = identifier
stack.append(neighbor)
groups.append(members)
return component, groups
def condensation_edges(graph, component):
return sorted({
(component[u], component[v])
for u, neighbors in enumerate(graph)
for v in neighbors
if component[u] != component[v]
})
調用 condensation_edges 時,應使用同一圖所傳回的編號。DAG 有 len(groups) 個頂點,即使部分頂點沒有相連邊,沒有在傳回邊串列出現,也仍然存在。集合移除重複跨分量弧,排序則令頂點對較容易檢視;SCC 證明不需要排序。
空圖的兩個迴圈都不執行,結果是 ([], [])。自環只會遇到已標記頂點;重複弧可能令邊被檢查多次,但不改變可達性。程式不依賴遞歸深度。
例題 10.2.8
(成員次序不同於數學上的分量集合)
八頂點例子中,程式傳回 。中間的 來自轉置搜尋次序,數學分量則是集合 。為顯示而排序成員串列,不會改變劃分。
若再加一條 ,或在 7 加自環,沒有任何 SCC 改變。在這個遍歷次序下,已排序凝聚邊串列仍為 。孤立編號 0 仍然代表 ,即使任何邊對都不含 0。
複雜度與輸出的含義
令 計算列出的全部弧,包括重複項。建立轉置圖需 時間及儲存。每遍中,每頂點至多推入一次,每條列出弧至多檢查一次;第一遍框架會接續原索引,不會每次重掃鄰接串列。因此找分量需 時間,及 額外儲存單元,包含轉置圖、堆疊和輸出。
可選的排序邊輔助函數有額外成本。若 是不同跨分量頂點對的數目,掃描鄰接串列並用雜湊集合建立邊集,期望需 時間;之後排序需 次比較,並需 額外單元。不要把排序輸出也算進無條件線性時間的保證。這些是普通圖操作及儲存單元界,不是任意大標籤的位元複雜度界。
反例模式
分量編號較小,不證明可以到達另一分量
例子中,孤立分量 得編號 0, 得編號 1,但前者沒有路徑到後者。拓撲次序保證已存在的跨分量路徑會向較大編號前進,並不保證每個小編號都能到達每個大編號。
同樣,改變根或鄰居次序,可能改變編號,卻不改變 SCC 劃分。比較劃分時應比較共同成員關係,不應期待每個分量有一個普遍固定的數字標籤。
凝聚圖方便之後處理依賴,但在每個最優化問題中,SCC 並不自動等於一個無成本頂點。若後續題目關心分量內的路徑長度、容量或到訪限制,就必須另行論證內部細節。劃分證明的是互相可達,不會抹去原圖的所有其他性質。
常見錯誤
(用凝聚圖計算分量內部的距離)
把有向環 縮成一個頂點,就丟掉了從 到 的最短路徑有兩條弧這個資訊。凝聚圖只記錄哪些分量能到達哪些分量;分量內部的路徑長度、容量和訪問限制需要另外論證。
練習與完整解答
快速檢查
(1. 為何孤立頂點不需要自環也構成 SCC?證明互相可達具有傳遞性,從而兩個 SCC 不能重疊。)
解答 · 1. 零長度路徑與串接建立劃分
零長度路徑使每個頂點都可到達自己,包括孤立頂點。若 且 ,串接 及 ,便得 。連同自反及對稱性,這是一個等價關係,等價類互不相交。若兩個互相可達的極大集合重疊,它們就必須是同一類。
快速檢查
(2. 八頂點例子中,{0,1,2}、{3,4}、{5,6} 的完成最大值各是多少?{7} 首先獲分量編號,為何不違反次序引理?)
解答 · 2. 完成最大值限制邊,而非無關分量
以 1 起計的完成排名計,它們依次是 7、4、2,凝聚邊遵循 。頂點 7 在排名 8 完成,所以其單點分量先被選中。它與其餘分量沒有連接邊,引理便沒有約束它與該分量鏈的相對次序。
快速檢查
(3. 單獨弧 的發現次序、完成次序和正確第二遍根次序各是甚麼?分別說明反向發現次序及沒有轉置為何失敗。)
解答 · 3. 完成事件與反向邊缺一不可
發現次序是 ,完成次序是 ,正確第二遍是在轉置圖按 考慮根。倒轉發現次序會先從 1 到達 0,錯誤合併。正確根次序若用在原圖,則會從 0 到達 1,也錯誤合併。正確次序配合轉置圖,才會分別分配兩個單點 SCC。
快速檢查
(4. 加入重複弧或自環,能否改變 SCC 劃分?它們不改變可達性,為何實作仍須在推入時標記?)
解答 · 4. 邊的重數不會創造新可達頂點對
重複弧提供的是原本已有的步驟;任何行走中的自環都可移除而不改變兩端。兩者都不會增加不同頂點間的互相可達關係。推入時立即標記,令之後的檢查馬上看見已發現狀態,避免因重複弧或環而重複推入。相同可達事實仍須以受控的堆疊工作來實作。
快速檢查
(5. 八頂點凝聚圖為何只有 (1,2) 及 (2,3),即使有兩條原圖弧從分量 1 指入頂點 3?DAG 有多少頂點?)
解答 · 5. 移除重複邊,但保留孤立頂點
及 都產生同一分量對 ,只需保留一份。 產生 ,其餘列出的邊都在分量內。DAG 有四個頂點,每組一個。孤立編號 0 透過頂點總數保留下來,即使它沒有在任何邊對出現。
快速檢查
(6. component[u] 小於 component[v],是否一定代表 u 能到達 v?輸出的次序真正支持哪個蘊涵方向?)
解答 · 6. 拓撲標籤限制路徑,卻不斷言路徑存在
不是:例子中頂點 7 的分量編號小於頂點 0,卻無法到達它。成立的是,若 能到達 且兩者分量不同,凝聚路徑至少有一條跨分量邊,每條都增加編號,所以 component[u] < component[v]。若兩者屬於同一分量,則互相可達,編號相等。