下列各節點排序中，何者是下圖 graph 的 topological order？
Ac, a, b, d, f, e, g, i, h, k, j
Ba, b, c, d, g, e, f, k, j, i,h
Cc, a, b, d, e, g, f, i, h, k, j正確答案
Da, e, i, k, b, d, f, h, j, c, g
答案與詳解
C
正確答案
拓撲排序要求所有有向邊 (u, v) 中，起點 u 必須排在終點 v 前面。逐一檢查選項是否違反圖中的箭頭方向即可秒解。
為什麼答案是 C
正確。檢查圖中所有有向邊，起點節點皆排在終點節點之前（如 a→b, e→f, h→k 等），完全符合拓撲排序的定義。
載入中…
完整詳解
Pro · 無限重點 拓撲排序要求所有有向邊 (u, v) 中，起點 u 必須排在終點 v 前面。逐一檢查選項是否違反圖中的箭頭方向即可秒解。
秒殺技巧
找選項中「後面的節點有箭頭指向前面的節點」的錯誤。A 的 f 在 e 前(錯，e→f)；B 的 g 在 e 前(錯，e→g)；D 的 k 在 b 前且 c 在最後(錯，c 是起點)。逐選項分析
A✕
錯誤。選項中 f 排在 e 前面，但圖中存在有向邊 e → f，前驅節點 e 必須排在後繼節點 f 之前，違反拓撲排序規則。
B✕
錯誤。選項中 g 排在 e 前面，但圖中存在有向邊 e → g，前驅節點 e 必須排在後繼節點 g 之前，違反拓撲排序規則。
C✓ 正確
正確。檢查圖中所有有向邊，起點節點皆排在終點節點之前（如 a→b, e→f, h→k 等），完全符合拓撲排序的定義。
D✕
錯誤。選項中 k 排在 b 前面，但圖中存在路徑 b → d → f → h → k；且 c 為起點卻排在最後，嚴重違反拓撲排序規則。
拓撲排序 (Topological Sort) 檢查法
| 有向邊關係 | 排序規則 | 本題應用範例 |
|---|---|---|
| u 指向 v (u → v) | u 必須排在 v 前面 | 圖中有 e → f，則 e 必須在 f 前 |
陷阱提醒
考生容易將拓撲排序的「前驅後繼」關係搞反，誤以為箭頭指向的節點要排在前面。牢記「箭頭起點 (前驅/原因) 必須先於箭頭終點 (後繼/結果)」。