Topological Sort

Graph Algorithm

Topological Sort (トポロジカル ソート)：
Directed Acyclic Graph（DAG：非循環有向グラフ) G=(V,E)に対し、
全vertexに対する線形順序で、G が edge (u, v) を含んでいれば、線形順序の中で uがvより先に現れる形へのVertex Sort。

Topological-Sort(G)
1. 各vertexの終了時刻 f[v]を計算するために、DFS(G)を呼び出す。
2. 終了vertexを連結リストの先頭に挿入する
3. retun vertexの連結リスト


[Reference]:

Introduction to Algorithms, Second Edition
アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)