トポロジカルソート
閉路のない有向グラフの辺が左から右に向くように頂点を左から右に一列に並べるソートのこと。
グラフがトポロジカルソート可能であるということは、そのグラフがDAGであることと等価。
物事の依存関係や因果関係などをモデル化するのに有効。MakefileやJOB Scheduleなどがある。
実装
トポロジカルソートの実装にはBFSまたはDFSを利用して実装できる。どちらの場合でも計算量は$O(|E|+|V|)$（E=辺、V=頂点）となる。
BFSを利用した場合
幅優先探索を利用する場合、各頂点の入次数を記録しておきます。
入次数がゼロの頂点がトポロジカルソートの開始位置となる。この頂点からBFSで探索を行います。
頂点から辺を辿って各頂点を見つけるたびに入次数を減らし、入次数がゼロになったものが次にBFSをおこなう頂点となる。
DFSを利用した場合
適当な頂点から探索を開始する。末尾まで探索が終わった後に頂点をたどるときの順番(帰りがけ順 postorder)の逆順がトポロジカルソートした結果となる。
前述の探索でまだ未チェックの頂点があれば同様の探索を繰り返すことでグラフのトポロジカルソートができる。
閉路検出
トポロジカルソートはその性質からトポロジカルソートができない＝グラフに閉路が存在することを確認できる。
BFSを利用している場合、すべての探索をおこなった場合、入次数がゼロにならない頂点が存在する。
DFSを利用した場合、すでに訪問したアクティブな頂点に再度訪問した場合、そのグラフに閉路が存在することを検出できる。