Q32.
下列有關拓樸排序法(Topological Sort)的敘述，下列何者正確？
電腦軟體設計共同科目 · 乙級 · Q32
難易度分析
2 / 5
本題考查對拓樸排序基礎定義、時間複雜度以及結果特性的理解。選項中涵蓋了容易混淆的唯一性陷阱與複雜度分析，要求考生能精確區分正確的圖論限制條件與演算法效能。
正確答案：①適用此法的有向圖形(Directed Graph)必須沒有循環(Acyclic)才有意義
① 適用此法的有向圖形(Directed Graph)必須沒有循環(Acyclic)才有意義:拓樸排序僅能應用於有向無環圖（DAG, Directed Acyclic Graph），因為若圖中存在循環（Cycle），則節點之間會形成相互依賴關係，無法產生合法的線性排序。
錯誤選項解析
- ② 用深度優先搜尋法(Depth-first Search)可產生的拓樸順序其序列具唯一性:使用深度優先搜尋（DFS）產生的拓樸順序並不具唯一性，同一個 DAG 可能存在多種合法的拓樸序列，DFS 的拜訪順序會影響最終結果，但並非唯一。
- ③ 對一個有V 個頂點，E 個邊的有向圖形作拓樸排序，需時O(VE):拓樸排序的時間複雜度為 O(V+E)，而非 O(VE)。無論是使用 DFS 或 Kahn 演算法（入度法），每個頂點與每條邊都僅需處理一次。
- ④ 一個有向圖形經拓樸排序後的結果為唯一:有向圖經拓樸排序後的結果不一定唯一。當圖中存在多個入度為零的頂點時，這些頂點的排列順序可互換，因此會產生多種合法的拓樸序列。
Learning Tip
"拓樸排序的核心考點在於確認圖必須為 DAG（有向無環圖），且時間複雜度恆為 O(V+E)。常考陷阱包括：誤以為拓樸序列唯一（實際上僅當圖為單一線性鏈時才唯一），以及混淆時間複雜度為 O(VE)。實務上常用於任務排程、編譯相依性分析與課程修課順序等場景。"
學員答題分佈
①適用此法的有向圖形(Directed Graph)必須沒有循環(Acyclic)才有意義0%
②用深度優先搜尋法(Depth-first Search)可產生的拓樸順序其序列具唯一性0%
③對一個有V 個頂點，E 個邊的有向圖形作拓樸排序，需時O(VE)0%
④一個有向圖形經拓樸排序後的結果為唯一0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！