拓撲排序：先穿襪子才穿鞋

早上出門的順序

穿衣服有依賴關係——

怎麼把這些步驟排出一個合法順序？ 這就是拓撲排序。

把依賴畫成有向圖：A → B 表示「A 要先於 B」。

⚠️必要條件：DAG

拓撲排序只能用在 DAG（有向無環圖）。有環的話——比如「A 要先於 B」、「B 要先於 A」——根本沒有合法順序，互相等死。

入度 (in-degree) = 指向我的箭頭數量。 入度為 0 的節點 = 沒有人要等它，可以馬上做。

步驟：

跑一遍上面那張圖：

輪	Queue	結果	入度變化
初始	[襪子, 襯衫]	[]	兩者入度都 0
取襪子	[襯衫, 褲子]	[襪子]	褲子入度 -1 → 0
取襯衫	[褲子, 外套]	[襪子, 襯衫]	外套 -1 → 0
取褲子	[外套, 鞋] (部分)	[襪, 衫, 褲]	鞋 -1
取外套	[鞋]	+外套	鞋 -1 → 0
取鞋	[出門]	+鞋	出門 -1 → 0
取出門	[]	+出門 ✓	—

最終：襪子 → 襯衫 → 褲子 → 外套 → 鞋 → 出門。

Algorithm KahnTopologicalSort(graph):

indeg ← 算每個節點的入度

queue ← 所有 indeg=0 的節點

result ← []

while queue not empty:

u ← queue.dequeue()

result.append(u)

for v in graph[u]:

indeg[v] ← indeg[v] - 1

if indeg[v] == 0: queue.enqueue(v)

if len(result) ≠ V: return “有環！不是 DAG”

return result

DFS 走訪每個節點，結束時把它推進 stack。最後 stack 反過來就是拓撲順序。

DFS(u):
  visited[u] = true
  for v in graph[u]:
    if not visited[v]: DFS(v)
  stack.push(u)   ← 後序

最後 reverse(stack) = 拓撲排序

為什麼這樣可以？ 因為 DFS 結束時，所有「我依賴的點」都已經被推進 stack 了——它們會在我之前出 stack（反轉後）→ 滿足依賴。

方法	怎麼偵測
Kahn	跑完 queue 後 `len(result) < V` → 有環
DFS	走訪時遇到「灰色」節點（正在處理中）→ 有環

兩種演算法都 O(V + E)——跟 BFS / DFS 一樣。

📝考試會這樣考

題型一：給 DAG，列出拓撲排序。 訣竅：跑一遍 Kahn 演算法。注意 queue 取出順序如果有平手，題目通常會說「按字母順序」。

題型二：給有向圖，判斷是否為 DAG。 跑 Kahn，若最後 result 不包含全部節點 → 有環，不是 DAG。

題型三：拓撲排序唯一嗎？ 答：通常不唯一。同層級的點順序可以交換。例如「襪子和襯衫」誰先誰後都行。

題型四：DFS 法為什麼用後序？ 答：因為 DFS 結束時，所有後代節點都已處理完成。後序入 stack、最後反轉，能保證依賴在前。