Q33.
下圖若以A 為起始點，針對下面之圖形(Graph)，以拓撲排序法(Topological Ordering)將節點之排序列出，下列之排列順序何者是錯誤的？
電腦軟體設計共同科目 · 乙級 · Q33
難易度分析
3 / 5
本題要求分析有向無環圖的節點相依關係，並從多個可能的合法排序中找出唯一不符合規則的選項。由於需逐一比對每個選項與所有有向邊的約束條件，且題目採取反向提問（尋找錯誤項），增加了判斷的複雜度。
正確答案：④ADCB
④ ADCB:ADCB 為錯誤的拓撲排序。若圖中存在 B→D 的有向邊，則 B 必須排在 D 之前，但此順序將 D 排在 B 之前，違反了拓撲排序的前驅條件，因此是無效排序。
錯誤選項解析
- ① ABCD:ABCD 為有效的拓撲排序。若圖中存在邊 A→B、A→C、B→D、C→D，則 A 最先，B 與 C 無先後依賴關係可互換，D 最後，此順序符合所有前驅節點優先於後繼節點的規則。
- ② ABDC:ABDC 為有效的拓撲排序。在 A 完成後，B 與 C 可獨立執行，若先處理 B 再處理 D（假設 D 僅依賴 B），最後處理 C，此順序仍滿足相依性約束。
- ③ ADBC:ADBC 為有效的拓撲排序。若 D 僅依賴 A 而不依賴 B 或 C，則 A 之後可直接接 D，此順序在特定圖結構下成立。
Learning Tip
"拓撲排序僅適用於有向無環圖 (DAG)，其核心規則為：對於每條有向邊 u→v，u 必須排在 v 之前。常考陷阱在於判斷哪些節點之間無相依性（可互換順序），以及識別違反前驅節點優先原則的錯誤選項。解題時需先從圖形中列出所有有向邊，再逐一驗證各選項是否滿足所有邊的順序約束。"
學員答題分佈
①ABCD0%
②ABDC0%
③ADBC0%
④ADCB0%
此答題分佈是根據學員在 LongePass 模擬考等實際作答紀錄計算而成。與考友分享這道歷屆試題與詳細解析！