動機
在有向圖中,由一個頂點可到達另一個頂點,並不代表反方向也可到達。強連通分量把彼此可達的頂點歸為一組,將這些組收縮之後便得到一個無圈結構。兩遍掃描算法利用深度優先搜尋的完成時間來選取分量的處理次序,使得在轉置圖中,每個分量與其餘的搜尋互相隔離。
證明依賴的是整個分量及其最大完成時間,而不是「一個分量的每個頂點都遲於另一個分量的每個頂點完成」。清楚區分這一點,可以避免次序論證中一個常見的錯誤。
定義
定義 3.5.1
(強連通分量與縮點圖)
設 為有限有向圖。若頂點 之間各自都能沿有向路徑到達對方,則稱 強連通;長度為零的路徑亦允許。強連通分量(SCC)是這個關係的一個等價類。縮點圖(condensation graph)為每個 SCC 設一個頂點;當 且原圖中存在一條由 中某頂點指向 中某頂點的邊時,縮點圖中有邊 。
定義 3.5.2
(轉置圖與分量的完成時間)
轉置圖 把每條邊反向。對 執行一次完整的深度優先搜尋(DFS):只要仍有未訪問的頂點,就從任一未訪問頂點重新開始,直至所有頂點都被訪問,並記錄每個頂點的完成時間。對 SCC ,令 為 中各頂點完成時間的最大值。
兩遍掃描程序按完成時間由大至小處理各頂點;每當遇到一個尚未分配的頂點,就在 中由它出發做一次 DFS,並忽略已分配的頂點。該次搜尋所找到的頂點構成一個輸出組。
定理
定理 3.5.3
(縮點圖與完成時間)
縮點圖是無圈的。若縮點圖中有邊 ,則對 的完整 DFS 滿足 。
定理 3.5.4
(兩遍掃描 SCC 算法)
兩遍掃描程序輸出的各組恰好就是 的各個 SCC。使用鄰接表時,兩遍搜尋以及轉置圖的構造所需的時間和空間均為 。
證明思路或證明
第一個證明涵蓋第一個定理的兩項結論。
證明
(縮點圖無圈,以及沿邊的完成時間)
互相可達關係按定義滿足自反性和對稱性,並藉路徑的拼接滿足遞移性,因此其等價類構成頂點集的一個劃分。若不同分量在縮點圖中構成一個有向圈,則沿該圈的路徑再加上各分量內部的路徑,會使圈上所有頂點彼此可達,它們便屬於同一個分量,這與分量互不相同矛盾。因此縮點圖是一個有向無圈圖(DAG)。
對於邊 ,比較 中頂點最先被發現的情形。設最先被發現的頂點 在 中。此刻 中其餘頂點都仍未被發現。在 內有一條路徑由 通向該邊的起點,該邊進入 ,再沿 內的路徑可到達 的每個頂點;這些頂點全都仍未被發現。因此 DFS 在從 返回之前會探索它們全部, 在 的每個頂點之後完成,故 。反之,設最先被發現的頂點 在 中。此時不存在由 到 的路徑:這樣的路徑與 合在一起會令兩個分量合併。由 出發的 DFS 會到達 的每個頂點,並在發現任何 的頂點之前令它們全部完成。 的每個頂點都在 的每個頂點之後被發現,因而也在其後完成,於是同樣有 。
第二個證明涵蓋兩遍掃描算法,是對第二遍各次搜尋的歸納。
證明
(第二遍的每次搜尋恰好輸出一個分量)
不變量:在每次第二遍搜尋開始前,已分配的頂點構成若干完整 SCC 的並集,而且每個已輸出的組都是一個 SCC。開始時沒有任何已分配頂點。
設 為完成時間最大的未分配頂點, 為它所屬的 SCC。 的所有頂點都未分配,而完成時間互不相同,所以 大於其餘每個餘下分量 的 。若某個餘下分量 在縮點圖中有邊 ,由第一個定理會得 ,這不可能。所以 是餘下分量中的源點。於是在 中,每條離開 的邊都終止於 內或某個已分配頂點。由於搜尋忽略已分配頂點,它不會離開 。反過來, 內任意兩個頂點在 中藉留在 內的路徑彼此可達(把 內的路徑反向,仍是 內的路徑),而 全部未分配,所以由 出發的搜尋能到達 的每個頂點。輸出的組恰好是 ,不變量得以保持。每個頂點最終都會被分配,所以各組恰好就是各 SCC。
使用鄰接表時,構造轉置圖以及每次完整的 DFS 對每個頂點和每條邊只掃描常數次。把完成次序反轉可藉堆疊或列表完成,所以總時間和額外空間均為 。
證明透視
第二遍可能從哪裏逃出
第二個證明只使用第一個定理一次:用來排除某個餘下分量有邊指向所選分量 。這也說明了為甚麼只比較最大值就足夠:完成時間最大的頂點 本身就是它所屬分量的最大值,不需要任何關於其他個別頂點的結論。
不顯而易見的一步是把邊反向。在 中, 完全可以有邊通向其他餘下分量,搜尋會沿這些邊走出去;完成時間定理只保證沒有餘下分量有邊指向 。把所有邊反向,恰好把這個保證變成「沒有邊離開 」。有兩個假設承擔了重量。搜尋必須跳過已分配頂點,因為由較早分配的分量指向 的原有邊,在 中會變成離開 的邊。起點必須取自第一遍的完成次序,因為只有這個次序才由定理與縮點圖的邊連繫起來。論證以歸納法完結:取走一個完整分量之後,餘下的分量仍按 排序,所以下一步仍可作同樣的選擇。
例題詳解
例題 3.5.5
(鏈狀排列的三個分量及其完成時間)
設邊為 、、、、 和 ,並按字母次序掃描鄰接表。第一遍 DFS 由 開始:先發現 ,再發現 和 (邊 與 都指向已被發現的頂點),最後發現 。 的發現時間依次為 。然後 在時間 完成, 在 , 在 , 在 , 在 。於是 、、:沿鏈 ,最大值遞減,與定理的預測一致。
轉置圖的邊為 、、、、 和 。完成時間遞減的次序是 。由 出發的搜尋只到達 :得到組 ,其後跳過 。由 出發的搜尋見到指向 的邊,但 已分配而被忽略,並到達 :得到組 ,其後跳過 。由 出發的搜尋忽略指向已分配頂點 的邊:得到組 。這三個組就是各個 SCC。
例題 3.5.6
(一條單向邊)
對於兩個頂點 且沒有返回路徑的情形,SCC 為 和 。僅有由 到 的可達性並不能令它們成為同一個分量。縮點圖只有一條邊 。
例題 3.5.7
(一個圈就是一個分量)
在有向圈 中,每個頂點都能到達另外兩個頂點。這三個頂點同屬一個 SCC,儘管任意兩個頂點之間並沒有雙向的直接邊。
常見錯誤
反例模式
一條邊並不代表互相可達
圖 中存在由 到 的路徑,但沒有返回的路徑。把有向可達性當作無向關係,會把兩個不同的分量錯誤地合併。
常見錯誤
(拿個別頂點的完成時間代替最大值作比較)
當縮點圖中有邊 時,定理比較的是最大完成時間 與 。它並沒有聲稱 中的每個頂點都遲於 中的每個頂點完成。在下面的例子中,、 且有邊 ,完成次序可以是 :雖然 , 中的 卻早於 中的 完成。
常見錯誤
(第二遍漏掉已分配頂點的記錄)
第二遍搜尋必須忽略先前搜尋已經分配的頂點,並且必須按第一遍所得的完成時間遞減次序選取起點。若在第二遍中重新計算完成次序,或讓搜尋重新進入已分配的頂點,就無法保證每次搜尋只停留在一個分量之內。
為甚麼完成時間的最大值已經足夠
深度優先搜尋在第一次訪問某個頂點時賦予其發現時間,在檢查完它所有的出邊並從遞歸後代返回之後賦予其完成時間。在通常的順序實作中,完成時間互不相同。一棵 DFS 樹可以包含來自多個 SCC 的頂點;定理並不要求每個分量在整個 DFS 森林中構成一棵連續的子樹。
考慮由分量 指向另一個不同分量 的一條邊。若這兩個分量中最先被發現的是 的某個頂點,則此刻除該起始頂點之外, 和 的所有頂點都仍未被發現。 內的路徑、通向 的邊以及 內的路徑顯示:最先被發現的那個 頂點可以經由這兩個分量中尚未訪問的頂點到達 的每個頂點。DFS 在從該 頂點返回之前,會令所有這些後代頂點完成。因此它的完成時間大於 中每個頂點的完成時間,從而推出最大值之間的不等式。
若最先被發現的是 的某個頂點,則邊 的存在排除了由 回到 的任何路徑。由該 頂點出發的 DFS 會到達 的全部頂點,但在完成之前無法發現 的任何頂點。因此每個 的頂點都在第一個 頂點被發現之前完成。這兩種情形在不預先假設 DFS 先訪問哪個分量的前提下,建立了同一個比較結論。
例題 3.5.8
(完成次序不一定把同一分量的頂點排在一起)
設 ,兩個方向的邊都有;設 ,並添加邊 。由 開始 DFS,並先探索 再探索 。完成次序可以是 。在此次序中,分量 與 交錯出現,但 是 的完成時間,它大於 。定理涉及的是最大值,而不是由各個時間構成的連續區段。
為甚麼第二遍能提取出整個分量
把所有邊反向會令每條路徑反向,所以在 中彼此可達的頂點在 中仍然彼此可達。SCC 的劃分保持不變,而縮點圖的每條邊都改變方向。在每次第二遍搜尋開始時,假定先前輸出的各組都是完整的分量;這就是歸納假設。
完成時間最大的未分配頂點所屬分量的最大值,在餘下分量中最大。若原縮點圖中另有一個餘下分量有邊指向它,則由完成時間定理,該前驅分量會有更大的最大值,這是不可能的。因此所選分量是餘下分量中的源點。在轉置圖中,它沒有指向其他餘下分量的邊。拒絕進入已分配頂點的搜尋無法離開所選分量,而轉置圖中的互相可達性又保證搜尋能到達該分量的每個頂點。於是得到的組恰好是一個 SCC,歸納假設得以保持。
在轉置圖中,由某個未分配分量指向已分配分量的邊不會令上述推理失效,因為搜尋明確地忽略已分配的頂點。若實作中開始新的 DFS 時不記錄先前的分配情況,就可能反覆遍歷已經輸出的頂點,也就不能直接體現所述的證明。所用的次序是由第一次圖搜尋得到的完成時間遞減次序,而不是在第二遍中重新計算的完成次序。
反例模式
在第二遍搜尋原圖
假設第二遍不在 而在 本身按完成時間遞減次序搜尋。取只有一條邊 的圖 。每次完整的 DFS 都使 先於 完成(由 開始,先完成 再完成 ;由 開始,先完成 ,其後才發現 )。遞減次序因此以 開始,而在 中由 出發的搜尋會到達 ,輸出變成單一組 。可是沒有由 回到 的路徑,所以 SCC 是 和 。在只有邊 的 中,由 出發只找到 ,下一次搜尋找到 。補救的方法是使用轉置圖:次序中的第一個頂點屬於源點分量,只有把邊反向之後,它才沒有指向其他餘下分量的邊。
一個可實現的執行過程
第一遍 DFS 可以在每個頂點完成時把它附加到一個列表中。倒著讀這個列表便得到完成時間遞減的次序,不需要數值形式的時間戳。構造 的方法是:對每條原有邊 添加邊 。把所有頂點初始化為未分配。掃描反轉後的完成列表;若某頂點已分配,則跳過。否則在 中運行一次圖搜尋,用當前的分量編號標記搜尋發現的每個頂點,並在搜尋結束時輸出該組。
第二遍可以使用 DFS 或其他窮盡式圖搜尋:證明所需要的是它恰好訪問轉置圖中由起點可達的未分配頂點。第一遍則必須使用 DFS 的完成時間。鄰接表令每條有向邊在每次遍歷中都能以常數時間取得。轉置圖的構造、兩次圖搜尋以及最後的掃描合計檢查 個條目。稠密的鄰接矩陣有不同的掃描成本,所以圖的表示方式是所述複雜度的一部分。
輸出的各組可用來構造縮點圖:掃描原圖的各條邊,只要兩個端點的編號不同就添加一條邊。同樣兩個分量之間的平行邊可以保留,也可以去重,視乎所需的表示而定;兩種選擇的可達性結構相同。SCC 算法並不會自動輸出某種特定的拓撲排序,除非事先訂明了它的慣例和次序。
檢驗一個給定的劃分
要驗證一個聲稱的分量,可以選一個代表頂點,只使用該組內的頂點,檢驗由它到組內每個頂點的可達性,以及由組內每個頂點回到它的可達性。把邊反向後,第二組檢驗就變成由該代表頂點出發的另一次搜尋。如果每個組在內部都是強連通的,並且把各組收縮之後得到的圖是無圈的,那麼這些組就是 SCC:更大的互相可達類會在不同的收縮組之間產生圈。
這個證明把內部連通性與極大性分開。僅僅證明每個給定的組是強連通的並不充分:把一個有向圈拆成若干單點組滿足這個局部條件,卻不滿足極大性。反過來,若某個組本身含有彼此不可達的頂點,那麼僅有各任意組構成的無圈圖也不充分。兩部分缺一不可。
沒有邊的圖中,每個頂點(包括孤立頂點)各自構成一個 SCC。空圖沒有分量。自環不會令其頂點與其他分量合併。這些情形都可由同樣的定義推出,兩遍掃描程序不需要為此設置特殊例外。
總結
互相可達性把有向圖劃分為各個 SCC,其縮點圖是 DAG。沿縮點圖的邊,DFS 完成時間的最大值遞減。在轉置圖中按完成次序遞減處理各頂點,每次可提取出一個餘下的源點分量。
練習
快速檢查
(頂點為 、只有一條邊 的圖,其 SCC 是甚麼?)
想一想 能否到達 。
解答 · 答案
它們是 和 ,因為 不能到達 。
快速檢查
(為甚麼縮點圖不能包含有向圈?)
把沿圈的路徑與各分量內部的路徑拼接起來。
解答 · 答案
一個圈會令圈上任意兩個分量之間在兩個方向上都有路徑,於是圈上所有頂點彼此可達,這些分量就不會互不相同。
快速檢查
(若縮點圖中有邊 ,哪個分量的最大完成時間較大?)
回想完成時間定理。
解答 · 答案
是邊的起點分量 :。
快速檢查
(為甚麼轉置會保持 SCC 的劃分?)
把每條邊反向後,一條路徑會變成甚麼?
解答 · 答案
把每條邊反向會令每條路徑反向。互相可達性在轉置圖中成立,當且僅當它在原圖中成立。
練習 3.5.9
(對頂點為 、邊為 、、、、、 的圖執行兩遍掃描算法,鄰接表按遞增次序掃描,並列出輸出的各組。)
核心
提示(1)
只需記錄頂點完成的先後次序,不必計算數值形式的時間。
解答(4)
- 1
由頂點 1 開始第一遍 DFS
搜尋依次發現 ;邊 指向已被發現的頂點,於是繼續到 和 ,邊 同樣被跳過。頂點完成的次序是 。
- 2
構造轉置圖並反轉完成次序
轉置圖的邊為 、、、、、。完成時間遞減的次序是 。
- 3
在轉置圖中搜尋並跳過已分配頂點
關鍵一步
由 出發,搜尋到達 再到達 ,得到組 ;其後跳過 和 。由 出發,指向 的邊因 已分配而被忽略,搜尋到達 :得到組 。
依據: 在轉置圖中由完成時間最大的頂點出發的搜尋無法離開它所屬的分量。
- 4
寫出各組並檢驗
輸出為 和 。它們就是各個 SCC: 與 都是圈,兩者之間只有邊 。這與定理一致:頂點 最後完成(時間 ),而 中的最大值較小(時間 )。