トポロジカルソート

トポロジカルソート（英: topological sort）は、グラフ理論において、有向非巡回グラフ（英: directed acyclic graph, DAG）の各ノードを順序付けして、どのノードもその出力辺の先のノードより前にくるように並べることである。有向非巡回グラフは必ずトポロジカルソートすることができる。

有向非巡回グラフのノードの集合に到達可能性関係 R (ノード x から y への(各辺の向きに逆行しない)経路が存在するとき、またそのときに限り xRy とする)を定めると、R は半順序関係となる。トポロジカルソートとは、この R を全順序になるように拡張したものとみなせる。

例

トポロジカルソートの典型的な利用例はジョブのスケジューリングである。トポロジカルソートのアルゴリズムはPERTというプロジェクト管理手法のスケジューリングのために1960年代初頭に研究が開始された。ジョブはノードとして表現され、XからYへの辺はジョブXが終了しなければジョブYを始められないということを意味する（例えば洗濯が完了しなければ服を乾燥機にかけられないなど）。ジョブをトポロジカルソートすると、ジョブに着手すべき順番がわかることになる。

コンピュータサイエンスでの利用例は、命令スケジューリング、表計算で式を変更したとき再計算が必要なセルの評価順序の決定、論理合成、Makefileで指定されたファイルのコンパイル順序の決定、リンカのシンボル依存関係の解決などがある。

左のグラフには次のように複数の結果にトポロジカルソートできる 7, 5, 3, 11, 8, 2, 9, 10 (見た目において左から右、上から下への順) 3, 5, 7, 8, 11, 2, 9, 10 (数値的に小さなノードを前に持ってくる) 3, 7, 8, 5, 11, 10, 2, 9 5, 7, 3, 8, 11, 10, 9, 2 (辺の数が少ないノードを前に持ってくる) 7, 5, 11, 3, 10, 8, 9, 2 (辺の数が多いノードを前に持ってくる) 7, 5, 11, 2, 3, 8, 9, 10

アルゴリズム

通常トポロジカルソートに使われるアルゴリズムはノードと辺の数に対して O(|V|+|E|) の線形な時間を必要とする。

Kahn (1962) が発明したアルゴリズムは、トポロジカルソートされた結果になるようにノードを順に選択していくというものである。まずは入力辺を持たない開始ノードを探してそれを集合Sに追加する。グラフに閉路がなければ少なくとも1つはそういうノードが存在する。その次に、

L ← トポロジカルソートした結果を蓄積する空リスト
S ← 入力辺を持たないすべてのノードの集合

while S が空ではない do
    S からノード n を削除する
    L に n を追加する
    for each n の出力辺 e とその先のノード m do
        辺 e をグラフから削除する
        if m がその他の入力辺を持っていなければ then
            m を S に追加する

if グラフに辺が残っている then
    閉路があり DAG でないので中断

グラフが無閉路有向グラフならば L が解となる（解は1つとは限らない）。そうでなければグラフには1つ以上の循環があり、トポロジカルソートは不可能である。

S は単なる集合だけではなくキューやスタックでもよい。集合 S からノード n が取り除かれる順番に応じて、異なる解が生成される。

深さ優先探索版

トポロジカルソートの別のアルゴリズムは深さ優先探索をベースにしている。このアルゴリズムではグラフの各ノードについて、トポロジカルソートを始めてからすでに訪れたノードに到達するまで深さ優先探索を行う。また、L への追加は先頭に行うことに注意。

L ← トポロジカルソートされた結果の入る空の連結リスト

for each ノード n do
    visit(n)

function visit(Node n)
    if n をまだ訪れていなければ then
        n を訪問済みとして印を付ける
        for each n の出力辺 e とその先のノード m do
            visit(m)
        n を L の先頭に追加

上のアルゴリズムでノードnがリストLに追加されるのは、ノードnが依存している他のノード（グラフ中でnから到達可能な全てのノード）を訪れた後であることに注意。このアルゴリズムでは、ノードnが追加されるときnが依存するすべてのノードはすでにリストLに追加されていることが保証されている。そのようなノードはノードnからvisit()の再帰で到達するか、あるいはnを訪れるより前にすでに到達されているはずである。辺とノードは一度しか訪問されないのでこのアルゴリズムは線形時間しか必要としない。上の擬似コードはグラフに循環がある場合にそれをエラーとして検出することはできない。この深さ優先探索ベースのアルゴリズムは『アルゴリズムイントロダクション』で解説されている。Tarjan (1976) が最初に発表したものと思われる。

閉路を検出するには、下記の擬似コードで行える。

L ← トポロジカルソートされた結果の入る空の連結リスト

for each ノード n do
    if n に印が付いていない then
        visit(n)

function visit(Node n)
    if n に「一時的」の印が付いている then
        閉路があり DAG でないので中断
    else if n に印が付いていない then
        n に「一時的」の印を付ける
        for each n の出力辺 e とその先のノード m do
            visit(m)
        n に「恒久的」の印を付ける
        n を L の先頭に追加

解の一意性

もしトポロジカルソートされたノードのすべてのノードが隣接する次のノードへの辺を持つなら、元の有向非巡回グラフはハミルトン路を含む。もしハミルトン路が含まれるなら、トポロジカルソートの結果は一意、つまり2つ以上の解は存在しない。逆に、トポロジカルソートがハミルトン路を作らないなら、元の有向非巡回グラフは2つ以上のトポロジカルソート結果を持つ。その場合、ある結果のうち直接辺によってつながっていないノードを交換することで2番目のトポロジカルソート結果を得ることができる。従って、一意なトポロジカルソート結果が存在するかどうか、あるいはハミルトン路が存在するかどうかは多項式時間で決定することができる。これに対し、一般のグラフにおけるハミルトン路の問題はNP困難である。

関連項目

• en:tsort (Unix) - トポロジカルソートを行う Unix プログラム
• make (UNIX) - プログラムのビルドを自動化する Unix プログラム

外部リンク

• NIST Dictionary of Algorithms and Data Structures: topological sort
• Weisstein, Eric W. "TopologicalSort". mathworld.wolfram.com (英語).