10.1 トポロジカルソートの定義
トポロジカルソートは、有向非巡回グラフ (DAG) の頂点を 線形に並べることです。これは、各エッジ (u, v) に対し、頂点 u が頂点 v に先行するということです。これはDAGでのみ可能で、サイクルを含むグラフでは実行できません。
この定義、どうだった？もし一発で理解できたなら、アルゴリズムにかなり詳しいかもね。
簡単に言えばこういうこと: タスク（グラフの頂点）リストとそれらの依存関係（グラフの矢印）リストがある。タスクを並べ替えて、「タスクA」が依存するすべてのタスクを先に実行できるようにするというわけ。そうすれば、「有向非巡回グラフの頂点の線形な並べ替え」なんてすぐにわかるよ。
トポロジカルソートは実践で非常に重要なアルゴリズムなので、著者の名前だけではなく、固有の名前があります。 これがどこで必要か一緒に見ていこう。
応用例：
1. タスクのスケジューリング:
依存するタスクをすべて完了した後で各タスクを実行できるよう順序を決定します。
例：
プロジェクト管理システムでのプロジェクト計画。
2. コードのコンパイル:
互いに依存するモジュールやソースコードファイルのコンパイル順序を決定します。
例：
ビルドシステムでのソフトウェアビルドの最適化（例: Makefile）。
3. パッケージマネージャーでの依存関係の解決:
パッケージを、その依存関係がすべてインストールされてからインストールできるように並べ替えます。
例：
パッケージマネージャー（例: npm, pip, apt）でのソフトウェアインストールプロセスを簡素化。
4. 経路の最適化:
依存関係を考慮して、地点やアクションの実行順序を決定します。
例：
物流および商品配送ルートの計画。
トポロジカルソートの時間と空間の計算量：
時間計算量：
トポロジカルソートの主要な2つのアルゴリズム（DFSとカーンのアルゴリズム）両方とも時間計算量は
O(V + E)です。Vは頂点の数で、Eはグラフのエッジの数です。
空間計算量：
両方のアルゴリズムの空間計算量はO(V + E)です。これはグラフの保存が必要であり、訪問済み頂点や先行頂点を追跡するための配列が必要だからです。
10.2 深さ優先探索 (DFS) による実装
トポロジカルソートは様々な方法で実行できますが、その一つが深さ優先探索（DFS）に基づいています。DFSのアルゴリズムは、完了したノードを追跡するためにスタックを使用します。
実装例：
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # 逆順で結果を返す
# 使用例：
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("トポロジカルソート:", result)
出力：
トポロジカルソート: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 実装: カーンのアルゴリズム
もう一つのアプローチはカーンのアルゴリズム（Kahn's Algorithm）と呼ばれます。カーンのアルゴリズムは、頂点の入次数の概念を利用しています。
実装例：
from collections import deque, defaultdict
def topological_sort_kahn(graph):
in_degree = {u: 0 for u in graph}
for u in graph:
for v in graph[u]:
in_degree[v] += 1
queue = deque([u for u in graph if in_degree[u] == 0])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("グラフにサイクルが含まれています")
# 使用例：
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("トポロジカルソート:", result)
出力：
トポロジカルソート: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION