トポロジカルソート

トポロジカルソートとは

トポロジカルソート（Topological Sort）は、グラフ理論における重要なアルゴリズムの一つで、有向非巡回グラフ（DAG: Directed Acyclic Graph）のノードを、その依存関係に基づいて順序付ける手法です。具体的には、どのノードも、そこから出力される辺の先のノードよりも前に来るようにノードを並べます。有向非巡回グラフであれば、必ずトポロジカルソートが可能であることが保証されています。

半順序関係と全順序関係

有向非巡回グラフのノード集合において、到達可能性関係R（ノードxからyへ辺を逆行せずに到達できる場合、xRyとする）を定義すると、Rは半順序関係となります。トポロジカルソートは、この半順序関係を全順序関係に拡張するものと解釈できます。

トポロジカルソートの応用例

トポロジカルソートは、様々な分野で応用されています。代表的な例として、以下のものがあげられます。

ジョブスケジューリング:
各ジョブをノードで表現し、ジョブ間の依存関係を辺で表現することで、ジョブの実行順序を決定できます。
コンピュータサイエンス:
命令スケジューリング、表計算における数式の評価順序の決定、論理合成、Makefileでのコンパイル順序の決定、リンカのシンボル依存関係の解決などに用いられます。

トポロジカルソートのアルゴリズム

トポロジカルソートには、主に以下の2つのアルゴリズムが用いられます。

1. Kahnのアルゴリズム

Kahnのアルゴリズムは、入力辺を持たないノードを順に選択していくことで、トポロジカルソートを実現します。具体的な手順は以下の通りです。

1. 入力辺を持たないノードをすべて集合Sに追加する。
2. リストL（トポロジカルソートの結果を格納する）を空で初期化する。
3. Sが空になるまで以下を繰り返す。
Sからノードnを削除し、Lに追加する。
nから出力される各辺eとその先のノードmについて、辺eを削除する。
もしmが他の入力辺を持たなくなったら、mをSに追加する。
4. もしグラフに辺が残っていれば、グラフに閉路があるためトポロジカルソートは不可能である。

集合Sは、キューやスタックで実装することも可能です。Sからノードを取り出す順序によって、複数のトポロジカルソート結果が得られる場合があります。

2. 深さ優先探索（DFS）に基づくアルゴリズム

深さ優先探索に基づくアルゴリズムでは、グラフの各ノードに対して深さ優先探索を行い、探索が完了したノードを結果リストの先頭に追加します。具体的な手順は以下の通りです。

1. リストL（トポロジカルソートの結果を格納する）を空で初期化する。
2. 各ノードnに対して、visit(n)を呼び出す。

`function visit(Node n)`

1. もしnがまだ訪問済みでなければ、nを訪問済みにする。
2. nから出力される各辺eとその先のノードmに対して、visit(m)を呼び出す。
3. nをLの先頭に追加する。

このアルゴリズムでは、ノードnがリストLに追加されるのは、nが依存している他のすべてのノードを訪問した後になります。このため、トポロジカルソートの順序が保証されます。また、各ノードと辺は一度しか訪問されないため、このアルゴリズムも線形時間で実行可能です。

閉路の検出

深さ優先探索に基づくアルゴリズムで閉路を検出するには、ノードに「一時的」と「恒久的」の印を付けます。

1. 各ノードnに対して、もしnに印が付いていなければvisit(n)を呼び出す。

`function visit(Node n)`

1. もしnに「一時的」の印が付いていれば、閉路が存在するため中断する。
2. もしnに印が付いていなければ、nに「一時的」の印を付ける。
3. nから出力される各辺eとその先のノードmに対して、visit(m)を呼び出す。
4. nに「恒久的」の印を付ける。
5. nをLの先頭に追加する。

解の一意性

トポロジカルソートの結果は、必ずしも一意ではありません。もし、トポロジカルソートされたすべてのノードが、隣接する次のノードへの辺を持つ場合、元の有向非巡回グラフにはハミルトン路が含まれます。ハミルトン路が含まれる場合、トポロジカルソートの結果は一意となります。逆に、トポロジカルソートの結果がハミルトン路を構成しない場合、複数のトポロジカルソート結果が存在します。このような場合、依存関係のないノードの順序を入れ替えることで、別のトポロジカルソート結果を得ることができます。

ハミルトン路の存在判定はNP困難ですが、トポロジカルソート結果の一意性は多項式時間で判定可能です。

まとめ

トポロジカルソートは、有向非巡回グラフのノードを、依存関係を考慮して順序付けるための重要なアルゴリズムです。ジョブスケジューリング、コンパイラの依存関係解決など、幅広い分野で応用されています。線形時間で実行可能な効率的なアルゴリズムが複数存在し、実用的なアルゴリズムとして広く活用されています。

参考文献

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

関連項目

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

もう一度検索