Graph Algorithms

Topological Sort

試想：有一 directed graph G，要如何對 G 上排列，使得 (u, v) 代表 u 要比 v 還更早出現 (complete)？

我們稱這種問題為 Topological Sort

• 如果 G 有 cycle，則一定不存在 ordering

• 如果 G 是 acyclic，則一定存在 ordering