用有向圖表示依賴
若任務 必須先於任務 ,便畫箭頭 。拓撲次序是一個把每個頂點列出一次的列表,並對每條箭頭都把 放在 前面。有向環令這種次序不可能存在:沿環的箭頭會要求某頂點排在自身之前。
假設圖是有限有向多重圖,有 個頂點及 條有向邊。平行箭頭須分別計算,自環也是有向環。我們只研究先後關係:拓撲次序本身不是考慮工期、資源限制或最短完成時間的排程。空圖的次序是空列表。
定義 4.3.1
(拓撲次序與有向環)
設 是頂點集為 的有限有向多重圖。
- 的拓撲次序是列表 : 中每個頂點恰出現一次,且對每條有向邊 ,頂點 都出現在 之前。
- 有向環是一列邊 ,其中 。當 時它是自環。
- 若 沒有有向環,便稱 無環。
移除沒有剩餘前驅的頂點
對每個頂點,維持尚未移除的頂點所誘導子圖中的入度。起初把所有入度為零的頂點放進隊列。反覆從隊列移除一個頂點、把它加入輸出,並對其每條出邊,把目的頂點的剩餘入度減一。當尚存目的頂點的入度降為零,便加入隊列;隊列為空時停止。
定理 4.3.2
(次序或有向環證書)
算法輸出全部頂點,當且僅當圖中沒有有向環。若全部頂點均輸出,其輸出次序就是拓撲次序;若提早停止,剩餘子圖必含有向環。
證明
(計數器、輸出次序與卡住的頂點集)
頂點從隊列取出後稱為已移除;頂點 的計數器是從未移除頂點指向 的邊數(計重數)。起初沒有頂點被移除,各計數器就是入度。移除 時,每條邊 令 的計數器減一次,所以計數器保持精確。頂點恰在計數器降為零(或起初為零)時進入隊列;計數器從不增加,因此每個頂點至多入隊一次,也就至多輸出一次。
次序。頂點 只在計數器為零時入隊,亦即它的所有前驅都已移除,而且在 被移除前計數器一直為零。所以輸出頂點之間的每條邊 , 都先於 輸出。若全部頂點都輸出,輸出就是拓撲次序。
提早停止。設隊列已空,而未輸出頂點集 非空。 中計數器為零的頂點本會入隊並被移除,所以 中每個頂點的計數器為正:它有一條來自 中頂點的入邊。從任一 出發,取 使 ,再取 使 ,如此類推。 有限,故有頂點重複,設 ,。把邊 連起來便是 內的有向環。
有環則不能完整輸出。若全部頂點都輸出,輸出便是拓撲次序,於是有向環 的頂點位置須滿足 ,這不可能( 時即 )。因此算法輸出全部頂點,當且僅當 無環。
證明透視
不變量與有限性用在哪裏
這個證明分兩半,用到不同的事實。次序的論證與卡住頂點集的論證都建基於同一個不變量:頂點的計數器等於它剩餘入邊的條數,並且按邊計算。這個等式是算法狀態(隊列為空)與圖結構(每個剩餘頂點都有剩餘前驅)之間唯一的橋樑。「有環則不能完整輸出」這一半完全沒有用到算法,只用到拓撲次序的定義。
不顯然的一步是在卡住的頂點集內沿前驅向後追蹤。它必然終止,因為集合有限;在無限圖上,例如整數集配邊 ,每個頂點都有前驅,卻沒有環。重複的頂點把追蹤路徑封閉成環。追蹤不必從環上開始:起點可以在環的下游,只有重複的那一段才是環。
要在提早停止後給出具體見證,可掃描剩餘圖的邊,為每個剩餘頂點記錄一個剩餘前驅。沿前驅指標走至頂點重複,再反轉重複的指標序列,便列出有向環。自環給出一條邊的見證。這次額外掃描與遍歷需 時間。
命題 4.3.3
(線性運行時間)
使用鄰接表時,算法需 次運算及 輔助空間(不計輸入圖與輸出列表)。
證明
(每個頂點與每條邊只處理一次)
計算全部入度時每條邊掃描一次。每個頂點至多入隊一次,因此至多被移除一次,移除時其每條出邊各掃描一次。總工作量是頂點的 加邊的 。隊列、計數器與輸出各至多存放 項。
掃描例子與容易誤解的剩餘頂點
例題 4.3.4
(獨立選擇可給出不同次序)
取頂點 ,邊為 、、 和 。起初 的入度為零。若先進先出隊列按此順序開始,移除 後 會在 後進入隊列,輸出為 。它符合四條箭頭;不同隊列次序可以得到其他有效拓撲次序。
例題 4.3.5
(停止的運行與有向環見證)
取 、、、、。計數器為 、、、、。只有 入隊;移除它後 降為 ,隊列便空了,輸出只有 。剩餘頂點是 ,為各自記錄一個剩餘前驅:、、、。從 出發,指標給出 , 重複。重複的部分是 ,反轉指標便得有向環 。這次追蹤從不在環上的 開始;而已輸出的 指向環,自己卻不在環上。
例題 4.3.6
(平行邊與自環)
取兩條平行邊 及一條邊 。計數器為 、、。移除 時 按每條邊各減一次,共減兩次而降為 ,所以 入隊;移除 後 降為 。輸出為 。再取只有一個頂點 並帶自環 的圖:它的計數器是 ,沒有計數器為零的頂點,隊列起初為空,輸出也是空的。剩餘圖是 ,,指標立即重複,見證便是一條邊的環 。
反例模式
剩餘頂點不一定都在環上
對 、、,沒有頂點入度為零,因此三個都留下。環是 ; 在環的下游而不在任何有向環上。提早停止只證明剩餘圖存在環,不代表每個剩餘頂點都屬於環。
常見錯誤
常見錯誤
(按鄰居而非按邊減少計數器)
設有兩條平行邊 ,且再沒有其他邊指向 。 的計數器起初是 。若實作對 的每個不同出鄰居只減一次,計數器只降到 , 便永不入隊,算法停止時 仍留下,並在無環圖上報告有環。計數器必須按邊計算,所以每條出邊都要減一次。
常見錯誤
(以為先進先出的輸出就是最小次序)
先進先出隊列不一定給出字典序最小次序。對 及孤立的 ,若隊列以 開始,會得到 ,但 更小。若要保證固定全序下的最小次序,需另設最小優先隊列規則並分析;任意先進先出順序沒有此保證。
練習
快速檢查
(對 、、 和孤立的 ,給出一個拓撲次序。)
先找出入度為零的頂點。
解答 · 答案
一個次序是 : 均先於 ,而 先於 。
快速檢查
(為何移除 時,兩條平行箭頭 要把入度減兩次?)
把計數器和剩餘圖比較一下。
解答 · 答案
兩條都是 的入邊,移除 時兩條都消失。若只減一次,計數器便與剩餘圖不一致。
快速檢查
(對 、、,指出一個環,以及一個不在該環但留下的頂點。)
先找出哪些頂點入度為零。
解答 · 答案
環為 ; 不在該環,但因前驅 尚在而留下。
快速檢查
(自環允許拓撲次序嗎?停止後算法能給出甚麼見證?)
想想該頂點要怎樣排在自己之前。
解答 · 答案
不允許:它要求頂點先於自身。追蹤其剩餘前驅指標可把該自環作為有向環見證。