TL;DR
DAG の各ノードに順序を付け、どのノードも出力先のノードより前に来るように並べ替えるソートのこと。
仕組み
DAG のすべてのノードを一列に並べ、各辺が「前のノードから後ろのノードへ」向くようにする。並べ替えた後は、辺の向きがすべて一方向にそろう。
Wikipedia によると、DAG なら必ずトポロジカルソートでき、ノード数と辺の数に対して線形時間で求められる。代表的な方法は 2 つある。
- Kahn の方法（1962 年）: 入ってくる辺のないノードを集め、1 つずつ取り出して結果に加え、そのノードから出る辺を消す。入ってくる辺がなくなったノードを新たに集めに加える。最後に辺が残っていれば閉路があり、DAG ではない
- 深さ優先探索を使う方法: 各ノードから再帰的にたどり、後ろのノードをすべて処理し終えたノードを結果の先頭に加える
例
Wikipedia によると、もともとは PERT によるジョブのスケジューリングの研究から生まれた。計算機科学では、Makefile でのコンパイル順の決定、表計算ソフトでのセルの再計算順の決定、リンカでのシンボルの依存関係の解決などに使われる。
注意点
解は 1 つとは限らない。直接の辺で結ばれていないノードどうしは入れ替えられるので、Kahn の方法でもノードを取り出す順によって別の解が得られる。