トポロジカルソートとは？仕組み・コード・計算量をわかりやすく解説

トポロジカルソートが解く問題

現実のタスクの多くには前提条件があります。科目には先に履修すべき科目があり、ソースファイルはインポートするファイルの後にコンパイルする必要があり、パッケージは依存先の後にインストールする必要があり、スプレッドシートのセルは参照先のセルの後に計算する必要があります。各タスクをノード、「先に行う必要がある」というルールを有向辺として描きます。トポロジカル順序とは、すべての辺を守るタスクの並びのことです。

順序が存在するのは、グラフに有向閉路がない場合に限ります。A が B を必要とし、B が A を必要とするなら、有効な順序は存在しません。よいトポロジカルソートは、無限ループに陥らずにそのことを報告します。DAGには通常、多くの有効な順序があり、アルゴリズムはそのうちの1つを返します。

考え方を言葉で説明すると

カーンのアルゴリズム（1962年にアーサー・カーン（Arthur Kahn）が発表）は、前から順に決めていきます。

1. 各ノードの入次数（入ってくる辺の数）を数えます。
2. 入次数が 0 のノードをすべてキューに入れます。これらは未達成の前提条件がないタスクです。
3. キューからノードを1つ取り出して結果に追加します。そのノードから出る各辺について、行き先の入次数を 1 減らし、0 になったら行き先をキューに追加します。
4. キューが空になったとき、結果にすべてのノードが含まれていればトポロジカル順序です。そうでなければ、残ったノードは閉路の一部です。

DFSによる方法は後ろから決めていきます。ノードは、それが指すすべてのノードが完了した後にようやく完了するため、完了した順の逆順に並べると、各ノードがその後続ノードすべてより前に来ます。

具体例で一歩ずつ確認

身支度の例です：下着 → ズボン、ズボン → 靴、靴下 → 靴、ズボン → ベルト、シャツ → ベルト、シャツ → ネクタイ、ネクタイ → ジャケット、ベルト → ジャケット。キューに入ったノードを先入れ先出しの順で取り出す、カーンのアルゴリズムで進めます。

最終的な順序は、下着、靴下、シャツ、ズボン、ネクタイ、靴、ベルト、ジャケットです。8つのノードがすべて並んだので、閉路はありません。

Pythonでの実装

dequeを使ったカーンのアルゴリズムです。

from collections import deque
def topo_sort(graph):
    """graph: dict node -> list of nodes that must come after it."""
    indegree = {n: 0 for n in graph}
    for n in graph:
        for m in graph[n]:
            indegree[m] += 1
    queue = deque(n for n in graph if indegree[n] == 0)
    order = []
    while queue:
        n = queue.popleft()
        order.append(n)
        for m in graph[n]:
            indegree[m] -= 1
            if indegree[m] == 0:
                queue.append(m)
    if len(order) != len(graph):
        raise ValueError("graph has a cycle")
    return order
dress = {
    "underwear": ["pants"], "socks": ["shoes"], "shirt": ["belt", "tie"],
    "pants": ["shoes", "belt"], "tie": ["jacket"], "belt": ["jacket"],
    "shoes": [], "jacket": [],
}
print(topo_sort(dress))
# ['underwear', 'socks', 'shirt', 'pants', 'tie', 'shoes', 'belt', 'jacket']

DFS版は、すべての後続ノードの処理が終わってからノードを追加し、最後にリストを反転します。

def topo_sort_dfs(graph):
    order, state = [], {}             # state: 1 = in progress, 2 = done
    def visit(n):
        if state.get(n) == 1:
            raise ValueError("graph has a cycle")
        if state.get(n) == 2:
            return
        state[n] = 1
        for m in graph[n]:
            visit(m)
        state[n] = 2
        order.append(n)
    for n in graph:
        visit(n)
    return order[::-1]
print(topo_sort_dfs(dress))
# ['shirt', 'tie', 'socks', 'underwear', 'pants', 'belt', 'jacket', 'shoes']

どちらの出力も有効です。Python 3.9以降は、標準ライブラリに graphlib.TopologicalSorter もあります。これは、各ノードからその先行ノードへの対応表を受け取る点に注意してください。上の辞書とは向きが逆です。

from graphlib import TopologicalSorter
ts = TopologicalSorter({"b": {"a"}, "c": {"a", "b"}})   # node: its prerequisites
print(list(ts.static_order()))  # ['a', 'b', 'c']

時間計算量と空間計算量

バリエーションとよくある間違い

• 最小の順序を優先：キューを最小ヒープ（heapq）に置き換えると、取り出せるノードのうち常に最小のものを選べます。辞書順で最小の順序が O((V + E) log V) で得られます。
• 並列スケジューリング：カーンのアルゴリズムを、入次数 0 のノードをまとめて取り出す形でラウンドごとに進めます。各ラウンドは同時に実行できるタスクのまとまりで、ラウンド数は最長の依存チェーンの長さです。graphlib.TopologicalSorter は get_ready() と done() でこれに対応しています。
• DAG上の最長経路・最短経路：辺をトポロジカル順に緩和すると、負の重みがあっても O(V + E) で答えが得られます。
• 異なる順序の数を数えるのははるかに難しい問題です。大きなグラフで、すべての順序を列挙しようとしないでください。

再帰版のDFSは、Pythonのほかの再帰版DFSと同じ再帰上限の問題があります。何千ものノードが連なる場合は、カーンのアルゴリズムを使ってください。

使う場面と実世界での用途

• Makeなどのビルドツールは依存関係に従ってターゲットを並べ、パッケージマネージャーは依存関係グラフに従ってインストール順を決めます。
• スプレッドシートは依存関係の順にセルを再計算し、循環参照を報告します。
• タスクスケジューラやワークフローエンジン（たとえばDAGベースのデータパイプライン）は、トポロジカル順序でタスクを実行します。
• コンパイラは宣言の順序づけや式グラフの評価に使い、データベースは外部キーの作成や削除の順序づけに使います。
• コーディング面接の問題：コーススケジュール I と II、エイリアン辞書（ソート済みの単語から文字の順序を求める）、並列コース、ビルド計画の最小の高さ。