Q70.
下列有關拓樸排序法(Topological Sort)的敘述，何者為錯誤？
電腦軟體設計共同科目 · 乙級 · Q70
難易度分析
3 / 5
本題要求辨析拓樸排序的正確定義與實現細節。選項中包含對演算法時間複雜度的認知以及對圖論特性的理解，特別是在演算法具體執行步驟上設計了精細的辨析陷阱，需對核心概念有精準掌握才能正確判斷。
正確答案：②用深度先搜尋法(Depth-First Search)可產生具拓樸順序的序列
② 用深度先搜尋法(Depth-First Search)可產生具拓樸順序的序列:單純執行 DFS 並無法直接產生拓樸順序，必須記錄各頂點的完成時間（Finish Time），並依完成時間的反序輸出才能得到正確的拓樸序列；或使用 Kahn 演算法（基於入度計算）亦可實現，此敘述過於簡化而錯誤。
錯誤選項解析
- ① 適用此法的有向圖形(Directed Graph)必須沒有循環(Acyclic)才有意義:拓樸排序僅能應用於有向無環圖（DAG），若圖中存在循環（Cycle）則無法產生合法的線性序列，此敘述正確。
- ③ 對一個有V 個頂點，E 個邊的有向圖形作拓樸排序，需時O(V+E):無論採用 DFS 法或 Kahn 演算法，拓樸排序的時間複雜度均為 O(V+E)，因為每個頂點與每條邊都僅需遍歷一次，此敘述正確。
- ④ 一個有向圖形經拓樸排序後的結果可能超過一個:當圖中存在多個入度為零的頂點，或某些頂點之間無相依關係時，拓樸排序的結果會有多種合法排列，此敘述正確。
Learning Tip
"本題考拓樸排序的核心概念與時間複雜度。常考陷阱在於混淆「DFS 本身」與「DFS 加完成時間反序」的差異；另外需留意拓樸排序不具唯一性，只要滿足所有前驅後繼關係即為合法序列。實務上常用於任務排程、編譯相依性分析及課程修課順序等場景。"
學員答題分佈
①適用此法的有向圖形(Directed Graph)必須沒有循環(Acyclic)才有意義0%
②用深度先搜尋法(Depth-First Search)可產生具拓樸順序的序列0%
③對一個有V 個頂點，E 個邊的有向圖形作拓樸排序，需時O(V+E)0%
④一個有向圖形經拓樸排序後的結果可能超過一個0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！