2. 拓撲排序問題 (Topological Sort Problem) 1. 問題描述： 對於一個有向無環圖 (DAG) G=(V,E)，找到其頂點的一個線性排序，使得對於圖中任意一條有向邊 (u,v)，頂點 u 在此排序中都出現在頂點 v 之前。 2. 問題分類/類型： 排序問題、圖論問題。 3. 問題的時間複雜度 (Problem Complexity)： 可以使用基於 DFS 的演算法在 Θ(V+E) 時間內解決。 4. 已知的主要解法/演算法： 基於深度優先搜尋 (DFS) 的演算法。 拓撲排序 (Topological Sort) 1. 演算法名稱： 拓撲排序 (Topological Sort) 2. 為了解決什麼問題： 對於一個有向無環圖 (DAG) G=(V,E)，產生一個所有頂點的線性排序，使得如果圖 G 中存在一條邊 (u, v)，則 u 在排序中出現在 v 之前。 3. 核心思想/主要步驟： 呼叫 DFS(G) 來計算每個頂點 v 的完成時間 f[v]。 當每個頂點完成時 (即 DFS-Visit(v) 結束，v 變為黑色)，將其插入到一個連結串列的前端。 返回該連結串列。 (連結串列中的頂點順序即為拓撲排序的逆序，或者說，按完成時間 f[v] 降序排列的頂點序列即為一個拓撲排序。) 4. 時間複雜度 (Time Complexity)： Θ(V+E) (主要由 DFS 決定，插入連結串列前端的操作是 O(1)) 5. 空間複雜度 (Space Complexity)： O(V) (用於 DFS 和儲存結果連結串列) 6. 輸入 (Input) / 輸出 (Output)： 輸入： 有向無環圖 (DAG) G=(V,E)。 輸出： 一個包含所有頂點的線性排序的連結串列。 7. 優點/缺點/限制： 優點： 提供了一種有效的任務排程或依賴關係排序的方法。 限制： 僅適用於有向無環圖 (DAG)。如果圖中有環，則無法進行拓撲排序。