アルゴリズムは次のように説明できます:
n 個の頂点と m 個のエッジを持つ有向グラフが与えられます。各エッジが小さい番号の頂点から大きい番号の頂点につながるように、頂点の番号を付け直す必要があります。
言い換えれば、グラフのすべての辺によって与えられる順序に対応する頂点の順列 (トポロジカル順序) を見つける必要があります。
深さ優先検索 (dfs(v)) を使用します
\(dfs(v)\) から終了するときにリストの先頭に頂点を追加すると、最後にこのリストでは、トポロジカルなソートが得られます。
したがって、目的のトポロジー ソート —これは退出時間の降順で並べ替えられています。