資料結構與演算法
工作 A～E 有「A 在 C 之前」「B 在 C 之前」「C 在 D 之前」「B 在 E 之前」「E 在 D 之前」的順序限制。滿足所有限制的工作順序（拓撲排序的結果）為下列何者？
- AA, C, B, E, D
- BB, A, E, C, D
- CB, E, D, A, C
查看答案與解析
正確答案：B. B, A, E, C, D
在 B, A, E, C, D 中，A 與 B 在 C 之前，C 與 E 在 D 之前，B 在 E 之前，5個限制全部滿足。A, C, B, E, D 在 B 之前進行 C，違反「B 在 C 之前」；B, E, D, A, C 在 C 之前進行 D，違反「C 在 D 之前」。拓撲排序是在有方向且無環路的圖（DAG）中，把頂點排列成所有邊都由前指向後的操作，可以用反覆取出沒有進入邊之頂點的方法（Kahn 演算法）或深度優先搜尋求得。答案不一定只有一個，這個例子中滿足限制的順序有5種。
- A. 在 B 之前進行 C，違反「B 在 C 之前」。
- B. 正確。5個限制全部滿足。
- C. 在 C 之前進行 D，違反「C 在 D 之前」。