拓撲排序：秩序的藝術

演算法背後的故事：北極星飛彈危機

20 世紀 50 年代末，美國海軍正在建造「北極星」核子潛艇。這是一個極其龐大的工程：涉及數千家承包商、數萬個任務和數百萬個零組件。複雜程度令人窒息。如果船體封閉前導航系統還沒準備好，整個專案就會失敗。

為了管理這種混亂，她們開發了 PERT (計畫評核術)。PERT 的核心是一個簡單的邏輯要求：「在一個任務的所有前置條件完成之前，妳不能開始這個任務。」

這個邏輯就是 拓撲排序 (Topological Sorting)。它將一團亂麻般的依賴關係，梳理成了一條筆直的、可執行的流水線。

為什麼需要它？

拓撲排序是任何 依賴管理系統 的脊樑。

• 套件管理器： npm install 或 pip install。如果函式庫 A 依賴函式庫 B，那麼 B 必須 先被安裝。
• 建置系統： Webpack, Make, 或 Docker。妳不能在原始碼編譯完成前去連結二進位檔案。
• 選課系統： 妳不能在修完「微積分 I」之前去修「高等微積分」。

如果存在循環（例如：A 依賴 B，而 B 又依賴 A），系統就會崩潰。這就是可怕的 「循環依賴 (Circular Dependency)」，而拓撲排序正是檢測它的工具。

演算法是如何「思考」的 (Kahn 演算法)

最直觀的實作方式是 Kahn 演算法 (1962)。它的思考方式就像一位工廠經理。

1. 盤點 (入度統計)： 她走過工廠車間，詢問每一個任務：「現在有多少事情擋著妳？」

   • 「我缺 3 個零件。」 (入度 = 3)
   • 「我啥也不缺，隨時可以開始！」 (入度 = 0)

2. 解鎖： 她尋找那些 零依賴 的任務。這些是「啟動者」。經理把她們放到輸送帶（佇列）上。

3. 漣漪效應： 當一個「啟動者」任務完成後，經理向工廠宣佈這一消息。

   • 那些正在等待她的任務歡呼道：「太好了！我等的東西少了一樣。」
   • 她們的依賴計數減 1。
   • 如果某個任務的計數降到了 0，她就大喊：「我解鎖了！」並跳上輸送帶。

4. 結果： 任務跳上輸送帶的順序，就是 拓撲序。

工程決策：死結檢測器

在工程中，拓撲排序有兩個目的：

1. 排序： 給妳一個合法的執行序列。
2. 環檢測： 如果演算法結束了，但還有任務沒被處理（因為她們的依賴計數永遠沒有降到 0），這意味著圖中存在 環。在建置系統中，這會拋出「Circular Dependency Error」。

它的時間複雜度是線性的 $O(V+E)$，這使得即使面對包含數百萬節點的依賴圖，它也能瞬間完成。

實作參考 (Python)

from collections import deque, defaultdict

def topological_sort(num_courses, prerequisites):
    """
    Kahn 演算法實作的拓撲排序。
    輸入: num_courses (int), prerequisites (List[List[int]]) -> [課程, 依賴]
    """
    # 1. 初始化：構建圖並統計依賴數 (入度)
    graph = defaultdict(list)
    indegree = {i: 0 for i in range(num_courses)}
    
    for course, pre in prerequisites:
        graph[pre].append(course) # pre 解鎖 course
        indegree[course] += 1

    # 2. 解鎖：找到所有 0 依賴的任務
    queue = deque([node for node in indegree if indegree[node] == 0])
    result_order = []

    # 3. 漣漪效應
    while queue:
        # 執行任務
        current = queue.popleft()
        result_order.append(current)
        
        # 通知鄰居
        for neighbor in graph[current]:
            indegree[neighbor] -= 1
            # 如果鄰居自由了，加入佇列
            if indegree[neighbor] == 0:
                queue.append(neighbor)

    # 4. 環檢測
    if len(result_order) != num_courses:
        raise ValueError("檢測到循環依賴！無法生成有效排程。")
        
    return result_order

# 使用範例
# tasks = 4
# deps = [[1, 0], [2, 1], [3, 2]] # 0 -> 1 -> 2 -> 3
# print(topological_sort(tasks, deps))

小結

拓撲排序是圖的「拉鍊」。它將一團糾纏不清的依賴網絡，拉成一條筆直的行動線。無論是建造核子潛艇還是打包 JavaScript 檔案，它都確保了我們永遠不會本末倒置。