トポロジカルソート（）とは、グラフ理論において、有向非巡回グラフ（）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。有向非巡回グラフのノードの集合に到達可能性関係 "R" (ノード "x" から "y" への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り "xRy" とする)を定めると、"R" は半順序関係となる。トポロジカルソートとは、この "R" を全順序になるように拡張したものとみなせる。トポロジカルソートの典型的な利用例はジョブのスケジューリングである。トポロジカルソートのアルゴリズムはPERTというプロジェクト管理手法のスケジューリングのために1960年代初頭に研究が開始された。ジョブはノードとして表現され、XからYへの辺はジョブXが終了しなければジョブYを始められないということを意味する（例えば洗濯が完了しなければ服を乾燥機にかけられないなど）。ジョブをトポロジカルソートすると、ジョブに着手すべき順番がわかることになる。コンピュータサイエンスでの利用例は、命令スケジューリング、表計算で式を変更したとき再計算が必要なセルの評価順序の決定、論理合成、Makefileで指定されたファイルのコンパイル順序の決定、リンカのシンボル依存関係の解決などがある。通常トポロジカルソートに使われるアルゴリズムはノードと辺の数に対して O(|V|+|E|) の線形な時間を必要とする。グラフが無閉路有向グラフならば L が解となる（解は1つとは限らない）。そうでなければグラフには1つ以上の循環があり、トポロジカルソートは不可能である。S は単なる集合だけではなくキューやスタックでもよい。集合 S からノード n が取り除かれる順番に応じて、異なる解が生成される。トポロジカルソートの別のアルゴリズムは深さ優先探索をベースにしている。このアルゴリズムではグラフの各ノードについて、トポロジカルソートを始めてからすでに訪れたノードに到達するまで深さ優先探索を行う。また、L への追加は先頭に行うことに注意。上のアルゴリズムでノードnがリストLに追加されるのは、ノードnが依存している他のノード（グラフ中でnから到達可能な全てのノード）を訪れた後であることに注意。このアルゴリズムでは、ノードnが追加されるときnが依存するすべてのノードはすでにリストLに追加されていることが保証されている。そのようなノードはノードnからvisit()の再帰で到達するか、あるいはnを訪れるより前にすでに到達されているはずである。辺とノードは一度しか訪問されないのでこのアルゴリズムは線形時間しか必要としない。上の擬似コードはグラフに循環がある場合にそれをエラーとして検出することはできない。この深さ優先探索ベースのアルゴリズムは『アルゴリズムイントロダクション』で解説されている。 が最初に発表したものと思われる。閉路を検出するには、下記の擬似コードで行える。もしトポロジカルソートされたノードのすべてのノードが隣接する次のノードへの辺を持つなら、元の有向非巡回グラフはハミルトン路を含む。もしハミルトン路が含まれるなら、トポロジカルソートの結果は一意、つまり2つ以上の解は存在しない。逆に、トポロジカルソートがハミルトン路を作らないなら、元の有向非巡回グラフはは2つ以上のトポロジカルソート結果を持つ。その場合、ある結果のうち直接辺によってつながっていないノードを交換することで2番目のトポロジカルソート結果を得ることができる。従って、一般のグラフにおけるハミルトン路の問題はNP困難であるが、一意なトポロジカルソート結果が存在するかどうか、あるいはハミルトン路が存在するかどうかは多項式時間で決定することができる。

出典:wikipedia