アルゴリズム

[Python] トポロジカルソートで有向非巡回グラフをソートする

2025-04-15更新日: 2025-04-15

トポロジカルソートは、有向非巡回グラフ(DAG: Directed Acyclic Graph)の頂点を、各辺の方向に従って並べる手法です。

DAGはサイクルを持たないため、トポロジカル順序が必ず存在します。

Pythonでは、深さ優先探索(DFS)や入次数を利用したアルゴリズム(Kahnのアルゴリズム)で実装できます。

DFSでは、各頂点を訪問後にスタックに積み、最終的にスタックを逆順にすることでトポロジカル順序を得ます。

目次から探す

トポロジカルソートとは
トポロジカルソートのアルゴリズム
Pythonでのトポロジカルソートの実装
完全なサンプルコード
トポロジカルソートの応用例
トポロジカルソートのパフォーマンス最適化
まとめ

トポロジカルソートとは

トポロジカルソートは、有向非巡回グラフ(DAG)において、ノードを特定の順序で並べる手法です。

この順序は、各ノードが持つ依存関係を考慮しており、親ノードが子ノードの前に来るように配置されます。

トポロジカルソートは、タスクの依存関係を解決する際や、コンパイル順序の決定、プロジェクト管理など、さまざまな分野で利用されます。

トポロジカルソートを行うことで、効率的に処理を進めることが可能となります。

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

深さ優先探索(DFS)によるトポロジカルソート

深さ優先探索(DFS)を用いたトポロジカルソートは、グラフの各ノードを訪問し、訪問が完了したノードをスタックに追加する方法です。

すべてのノードを訪問した後、スタックからノードを取り出すことで、トポロジカル順序が得られます。

このアルゴリズムは、再帰的に実装されることが一般的です。

以下は、DFSを用いたトポロジカルソートのサンプルコードです。

from collections import defaultdict
def dfs(node, visited, stack, graph):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, stack, graph)
    stack.append(node)
def topological_sort_dfs(graph):
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs(node, visited, stack, graph)
    return stack[::-1]  # スタックを逆順にして返す
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
# トポロジカルソートの実行
result = topological_sort_dfs(graph)
print(result)

['A', 'C', 'B', 'D']

Kahnのアルゴリズムによるトポロジカルソート

Kahnのアルゴリズムは、入次数を利用してトポロジカルソートを行う手法です。

まず、各ノードの入次数を計算し、入次数が0のノードをキューに追加します。

次に、キューからノードを取り出し、そのノードに接続されているノードの入次数を減らします。

入次数が0になったノードは再度キューに追加され、これを繰り返すことでトポロジカル順序を得ます。

以下は、Kahnのアルゴリズムを用いたトポロジカルソートのサンプルコードです。

from collections import defaultdict, deque
def topological_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for neighbors in graph.values():
        for neighbor in neighbors:
            in_degree[neighbor] += 1
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    sorted_order = []
    while queue:
        node = queue.popleft()
        sorted_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return sorted_order if len(sorted_order) == len(graph) else []  # サイクルがある場合は空リストを返す
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
# トポロジカルソートの実行
result = topological_sort_kahn(graph)
print(result)

['A', 'B', 'C', 'D']

DFSとKahnのアルゴリズムの違い

特徴	深さ優先探索 (DFS)	Kahnのアルゴリズム
アプローチ	再帰的にノードを訪問	入次数を利用してノードを処理
実装の複雑さ	簡単	やや複雑
サイクル検出	明示的には行わない	入次数が0のノードが残る場合、サイクルが存在する
メモリ使用量	スタックを使用	キューを使用

トポロジカルソートの計算量

トポロジカルソートの計算量は、使用するアルゴリズムによって異なりますが、一般的には以下のようになります。

深さ優先探索 (DFS): $O (V + E)$

ここで、 $V$ はノードの数、 $E$ はエッジの数です。

すべてのノードとエッジを一度ずつ訪問するため、線形時間で処理されます。

Kahnのアルゴリズム: $O (V + E)$

入次数の計算とキューの操作により、こちらも線形時間で処理されます。

このように、どちらのアルゴリズムも効率的にトポロジカルソートを行うことができます。

Pythonでのトポロジカルソートの実装

Pythonでのグラフの表現方法

Pythonでは、グラフを辞書(ディクショナリ)を使って表現することが一般的です。

各ノードをキーとして、そのノードに接続されているノードのリストを値として持つ形です。

以下は、グラフの例です。

graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

この例では、ノード’A’はノード’B’と’C’に接続されており、ノード’B’はノード’D’に接続されています。

ノード’D’は他のノードに接続されていないため、空のリストが割り当てられています。

DFSを用いたトポロジカルソートの実装

深さ優先探索(DFS)を用いたトポロジカルソートの実装は、以下のようになります。

再帰的にノードを訪問し、訪問が完了したノードをスタックに追加します。

from collections import defaultdict
def dfs(node, visited, stack, graph):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, stack, graph)
    stack.append(node)
def topological_sort_dfs(graph):
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs(node, visited, stack, graph)
    return stack[::-1]  # スタックを逆順にして返す
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
# トポロジカルソートの実行
result = topological_sort_dfs(graph)
print(result)

['A', 'C', 'B', 'D']

Kahnのアルゴリズムを用いたトポロジカルソートの実装

Kahnのアルゴリズムを用いたトポロジカルソートの実装は、以下のようになります。

入次数を計算し、入次数が0のノードをキューに追加して処理します。

from collections import defaultdict, deque
def topological_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for neighbors in graph.values():
        for neighbor in neighbors:
            in_degree[neighbor] += 1
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    sorted_order = []
    while queue:
        node = queue.popleft()
        sorted_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return sorted_order if len(sorted_order) == len(graph) else []  # サイクルがある場合は空リストを返す
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
# トポロジカルソートの実行
result = topological_sort_kahn(graph)
print(result)

['A', 'B', 'C', 'D']

Python標準ライブラリを使ったトポロジカルソート

Pythonの標準ライブラリには、トポロジカルソートを直接行うための関数はありませんが、networkxライブラリを使用することで簡単に実装できます。

以下は、networkxを使ったトポロジカルソートの例です。

import networkx as nx
# 有向グラフの作成
graph = nx.DiGraph()
graph.add_edges_from([('A', 'B'), ('A', 'C'), ('B', 'D'), ('C', 'D')])
# トポロジカルソートの実行
result = list(nx.topological_sort(graph))
print(result)

['A', 'B', 'C', 'D']

実装時の注意点とエラーハンドリング

トポロジカルソートを実装する際には、以下の点に注意が必要です。

サイクルの検出: 有向非巡回グラフ(DAG)でない場合、トポロジカルソートは不可能です。

Kahnのアルゴリズムでは、入次数が0のノードが残る場合、サイクルが存在することを示します。

ノードの存在確認: グラフに存在しないノードを訪問しないように、事前にノードの存在を確認することが重要です。
エラーハンドリング: 入力グラフが空の場合や、ノードが不正な場合には、適切なエラーメッセージを表示するようにします。

例えば、空のリストを返すか、例外を投げることが考えられます。

完全なサンプルコード

以下に、深さ優先探索(DFS)とKahnのアルゴリズムを用いたトポロジカルソートの完全なサンプルコードを示します。

このコードでは、両方のアルゴリズムを実行し、結果を比較することができます。

from collections import defaultdict, deque
# 深さ優先探索を用いたトポロジカルソート
def dfs(node, visited, stack, graph):
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(neighbor, visited, stack, graph)
    stack.append(node)
def topological_sort_dfs(graph):
    visited = set()
    stack = []
    for node in graph:
        if node not in visited:
            dfs(node, visited, stack, graph)
    return stack[::-1]  # スタックを逆順にして返す
# Kahnのアルゴリズムを用いたトポロジカルソート
def topological_sort_kahn(graph):
    in_degree = {node: 0 for node in graph}
    for neighbors in graph.values():
        for neighbor in neighbors:
            in_degree[neighbor] += 1
    queue = deque([node for node in in_degree if in_degree[node] == 0])
    sorted_order = []
    while queue:
        node = queue.popleft()
        sorted_order.append(node)
        for neighbor in graph[node]:
            in_degree[neighbor] -= 1
            if in_degree[neighbor] == 0:
                queue.append(neighbor)
    return sorted_order if len(sorted_order) == len(graph) else []  # サイクルがある場合は空リストを返す
# グラフの定義
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}
# DFSを用いたトポロジカルソートの実行
result_dfs = topological_sort_dfs(graph)
print("DFSによるトポロジカルソートの結果:", result_dfs)
# Kahnのアルゴリズムを用いたトポロジカルソートの実行
result_kahn = topological_sort_kahn(graph)
print("Kahnのアルゴリズムによるトポロジカルソートの結果:", result_kahn)

DFSによるトポロジカルソートの結果: ['A', 'C', 'B', 'D']
Kahnのアルゴリズムによるトポロジカルソートの結果: ['A', 'B', 'C', 'D']

このコードでは、グラフを辞書で定義し、DFSとKahnのアルゴリズムをそれぞれ実行しています。

出力結果は、両方のアルゴリズムによるトポロジカルソートの結果を示しています。

ノードの順序は異なる場合がありますが、依存関係は正しく保たれています。

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

タスクの依存関係を解決する

トポロジカルソートは、タスクの依存関係を解決するために広く利用されます。

例えば、プロジェクトにおいて、あるタスクが他のタスクの完了を待つ必要がある場合、トポロジカルソートを用いることで、タスクを適切な順序で実行することができます。

これにより、効率的にプロジェクトを進めることが可能になります。

コンパイル順序の決定

プログラミングにおいて、ソースコードのファイル間に依存関係が存在する場合、トポロジカルソートを使用してコンパイル順序を決定することができます。

例えば、あるファイルが他のファイルに依存している場合、依存しているファイルを先にコンパイルする必要があります。

これにより、コンパイルエラーを防ぎ、スムーズなビルドプロセスを実現します。

プロジェクト管理ツールでの活用

プロジェクト管理ツールでは、タスクやサブタスクの依存関係を管理するためにトポロジカルソートが利用されます。

タスクの優先順位を決定し、依存関係に基づいてタスクをスケジュールすることで、プロジェクトの進行状況を可視化し、効率的なリソース配分を行うことができます。

これにより、チーム全体の生産性が向上します。

サイクル検出への応用

トポロジカルソートは、グラフにサイクルが存在するかどうかを検出するためにも利用されます。

Kahnのアルゴリズムを使用することで、入次数が0のノードが残る場合、グラフにサイクルが存在することがわかります。

この特性を利用して、データフローや依存関係の解析において、サイクルを検出し、問題を特定することができます。

データベースの依存関係解決

データベースにおいて、テーブル間の依存関係を管理するためにトポロジカルソートが利用されます。

例えば、外部キー制約がある場合、親テーブルのデータを先に挿入し、その後に子テーブルのデータを挿入する必要があります。

トポロジカルソートを用いることで、テーブルの挿入順序を決定し、データ整合性を保つことができます。

これにより、データベースの操作がスムーズに行えるようになります。

トポロジカルソートのパフォーマンス最適化

グラフのサイズに応じたアルゴリズム選択

トポロジカルソートを実行する際には、グラフのサイズや特性に応じて適切なアルゴリズムを選択することが重要です。

小規模なグラフでは、深さ優先探索(DFS)を用いた実装がシンプルで効率的ですが、大規模なグラフや複雑な依存関係がある場合は、Kahnのアルゴリズムが適していることがあります。

特に、入次数が多いノードが存在する場合、Kahnのアルゴリズムは効率的に処理を行うことができます。

メモリ使用量の削減

トポロジカルソートの実装において、メモリ使用量を削減するためには、データ構造の選択が重要です。

例えば、スタックやキューを使用する際には、必要なサイズを事前に確保することで、メモリの再割り当てを避けることができます。

また、グラフの表現方法を工夫し、隣接リストを使用することで、メモリの使用量を抑えることができます。

特に、疎なグラフの場合、隣接リストは効率的な表現となります。

並列処理による高速化

トポロジカルソートの処理を並列化することで、高速化を図ることができます。

特に、Kahnのアルゴリズムでは、入次数が0のノードを同時に処理することが可能です。

これにより、複数のノードを同時にキューに追加し、依存関係を解決することができます。

Pythonでは、multiprocessingモジュールを使用して、並列処理を実装することができます。

ただし、並列処理を行う際には、データの整合性や競合状態に注意が必要です。

入次数の計算を効率化する方法

入次数の計算は、トポロジカルソートのパフォーマンスに大きな影響を与えます。

入次数を計算する際には、グラフを一度走査するだけで済むように、エッジを追加する際に同時に入次数を更新する方法が有効です。

これにより、入次数の計算を別途行う必要がなくなり、全体の処理時間を短縮できます。

また、エッジの追加や削除が頻繁に行われる場合は、入次数を動的に管理するデータ構造を使用することで、効率的に入次数を更新することができます。

まとめ

この記事では、トポロジカルソートの基本やアルゴリズム、Pythonでの実装方法、応用例、パフォーマンス最適化の手法について詳しく解説しました。

トポロジカルソートは、タスクの依存関係を管理するためや、コンパイル順序の決定、データベースの整合性維持など、さまざまな場面で非常に有用な手法です。

これを機に、トポロジカルソートを実際のプロジェクトや問題解決に活用してみてはいかがでしょうか。