トポロジカルソート
通常トポロジカルソートに使われるアルゴリズムはノードと辺の数に対して O(|V|+|E|) の線形な時間を必要とする。
Kahn (1962) が発明したアルゴリズムは、トポロジカルソートされた結果になるようにノードを順に選択していくというものである。まずは入力辺を持たない開始ノードを探してそれを集合Sに追加する。グラフに閉路がなければ少なくとも1つはそういうノードが存在する。その次に、
グラフが無閉路有向グラフならば L が解となる(解は1つとは限らない)。そうでなければグラフには1つ以上の循環があり、トポロジカルソートは不可能である。
S は単なる集合だけではなくキューやスタックでもよい。集合 S からノード n が取り除かれる順番に応じて、異なる解が生成される。