第11章 有向圖與拓撲排序

11.1 箭頭代表必須先發生的條件

有限簡單有向圖的一條邊是有序對 (u,v)，記 u→v，且 u≠v。不放自環或同向重邊，但 u→v 與 v→u 可同時存在，這會構成長度 2 的有向環。入度數指有多少箭頭進入該點，出度指有多少箭頭離開；入度和與出度和都等於邊數。

拓撲排序列出所有頂點各一次，並讓每條 u→v 的 u 早於 v。有向環會迫使某點早於自己，故不能排序。無有向環的有向圖稱 DAG。若有限非空圖沒有入度 0 的點，從任一點反覆選一個前驅，必有第一次重訪。把兩次出現同一點之間的片段倒過來讀，就沿箭頭形成一個有向環。因此非空 DAG 至少有一個入度 0 的點。

Kahn 方法每次選一個目前入度 0 的點，放到排序的下一格，再刪該點與其出邊。若原圖無環，剩圖仍無環，故總能繼續到取完；每個點被取出時，原先指向它的前驅都已取出。空頂點圖的排序是空序列。若剩圖非空卻無入度 0 的點，前驅論證給出一個環。檢查單一排序提案時，須先核對頂點各一次，再逐邊核對順序。某個提案失敗時，仍可用上述程序檢查是否存在其他排序。

11.2 四個例題

例題1 同一張 DAG 可以有兩個答案

箭頭 A→B、A→C、B→D、C→D。初始只有 A 入度零；刪 A 後 B、C 都可選；D 等它們都取出才可選。因此合法排序恰為 ABCD 與 ACBD。

例題2 循環依賴不能排順序

箭頭 A→B、B→C、C→A。若有排序，必有 A 在 B 前、B 在 C 前、C 在 A 前，矛盾。三點各入度 1，演算法起步就停。

例題3 有向走法不能借用反向

有 A→B、B→C，從 A 可以沿箭頭到 C；從 C 沒有出邊，不能反走到 A。A 的入度／出度為 0／1，B 為 1／1，C 為 1／0。

例題4 沒有依賴的點可以插入多處

若三點只有 A→B，C 與其他無關。保留 A 在 B 前，把 C 放前、放中或放後，得到 CAB、ACB、ABC。只有一條邊不意味一定只有一個排序。

11.3 練習

1. B10-C11-Q01 三點只有 A→B、B→C，有幾種拓撲排序？
2. B10-C11-Q02 例題1的 ACDB 合法嗎？
3. B10-C11-Q03 三點無邊，拓撲排序有幾個？
4. B10-C11-Q04 A→B 和 B→A 是同一條邊嗎？可拓撲排序嗎？
5. B10-C11-Q05 A→C、B→C、C→D，初始可選哪些？
6. B10-C11-Q06 四點有向圖的總入度 5，總出度多少？
7. B10-C11-Q07 序列 ABA 對只有 A→B 的兩點圖能當拓撲排序嗎？
8. B10-C11-Q08 剩三個頂點，每個目前入度皆正；為什麼可判有向環？
9. B10-C11-Q09 若 A→B、B→C，能否加 C→A 而維持 DAG？
10. B10-C11-Q10 若 A→B、B→C，加入 A→C 會移除某個原合法排序嗎？

11.4 完整解答

Q01

A 必在 B 前，B 必在 C 前；三點都須出現，唯一是 ABC。

Q02

不合法。雖然 A 在 B、C 前，D 卻在 B 前，違反 B→D；將 B 移到 D 前即可成 ACBD。

Q03

所有排列都沒有邊約束，故有 3!=6 種。

Q04

不同。它們一前一後各要求相反的先後，形成兩點環，不存在排序。

Q05

A、B 沒有入邊，可任選其一；C 有兩條入邊，D 有一條，兩者都不能先取。

Q06

每條邊恰有一個出發端和一個到達端，故兩種總和都等於邊數 5。

Q07

不能。A 重複，序列不是所有頂點各一次；即使某次 A 在 B 前也不夠。

Q08

從剩圖任一點出發，反覆取一個剩圖中的前驅。因每點目前入度皆正，每步都能取到。剩圖有限，直到第一次遇到已見的點為止，把兩次遇見該點之間的片段反向讀，就得到沿箭頭的環。

Q09

不能。新增邊閉合 A→B→C→A 這個環，拓撲排序不可能。

Q10

不會。原來已強迫 A 在 B 前且 B 在 C 前，故 A 已在 C 前。新邊不新增有效限制。