Coding Interview Prep · レッスン

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

Q: 「Kahnのアルゴリズム：BFSトポロジカルソート」レッスンは無料ですか？

はい。「Kahnのアルゴリズム：BFSトポロジカルソート」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

Q: Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。

Q: 「Kahnのアルゴリズム：BFSトポロジカルソート」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

Q: このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

すべての頂点の入次数を計算し、入次数が0の頂点をキューに入れて処理し、閉路を検出しながらトポロジカル順序を生成します。

「Kahnのアルゴリズム：BFSトポロジカルソート」はCoddyKit上の無料Coding Interview Prepレッスンです。これはレッスン1/4です。下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

トポロジカルソートとは

トポロジカルソートとは、有向非巡回グラフ (DAG) のノードを並べ替え、すべての有向辺 u → v について、並び順で u が v より前になるようにすることです。これは、ビルドシステム、コースの履修計画、パッケージ管理など、依存関係を持つタスクの有効な実行順序を表します。有効なトポロジカル順序を持てるのは DAG だけであり、閉路があると不可能になります。

Kahn法：核心となる考え方

Kahn法は、BFS に基づくトポロジカルソートの手法です。重要な考え方は、入次数が 0（前提条件がない）のノードを順序の先頭に置けることです。そのノードを置いた後、削除して隣接ノードの入次数を減らします。新たに入次数が 0 になったノードを処理できるようになります。すべてのノードを配置するか、閉路を検出するまで（入次数が 0 以外のノードが残るまで）繰り返します。

入次数の計算

まず隣接リストを構築し、各ノードの入次数（入ってくる辺の数）を計算します。入次数が 0 のノードが開始地点です。これらのノードには依存関係がありません。辺が [(0,1),(0,2),(1,3),(2,3)] のグラフでは、入次数は 0→0、1→1、2→1、3→2 です。入次数 0 で始まるのはノード 0 だけです。

from collections import deque, defaultdict

def compute_in_degree(n, edges):
    in_degree = [0] * n
    graph = defaultdict(list)
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    return graph, in_degree

graph, ind = compute_in_degree(4, [(0,1),(0,2),(1,3),(2,3)])
print('In-degrees:', ind)  # [0, 1, 1, 2]

Kahn法の実装

入次数が 0 のすべてのノードをキューに追加します。各ノードを処理し、結果に追加した後、各隣接ノードの入次数を減らし、0 になったらキューに追加します。結果リストのノード数がグラフのノード数より少ない場合は、閉路が存在します。閉路の一部のノードは、最後までキューから取り出せなかったためです。

from collections import deque, defaultdict

def kahn_topological_sort(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    order = []
    
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    if len(order) == n:
        return order   # valid topological sort
    return []          # cycle detected

print(kahn_topological_sort(4, [(0,1),(0,2),(1,3),(2,3)]))

Kahn法による閉路検出

Kahn法では閉路もそのまま検出できます。len(order) < n の場合、入次数が 0 にならなかったためにキューへ追加されなかったノードがあり、それらは閉路の一部です。これは、色分けした visited 配列を管理するよりも簡潔です。閉路が存在することを示すため、空のリストを返します。

# Cyclic graph: 0->1->2->0
edges_cycle = [(0,1),(1,2),(2,0)]
result = kahn_topological_sort(3, edges_cycle)
print(result)  # [] (cycle detected)

# Acyclic graph
edges_dag = [(0,1),(1,2)]
result = kahn_topological_sort(3, edges_dag)
print(result)  # [0, 1, 2]

時間計算量と空間計算量

Kahn法では各ノードを1回だけ処理し（1回だけキューから取り出し）、各辺も1回だけ処理します（入次数を1回だけ減らします）。時間計算量はO(V + E)です。空間計算量は、隣接リストと入次数配列に O(V + E)、さらにキューに O(V) です。これは最適な計算量です。有効な順序を作るには、最低限すべてのノードと辺を読み取る必要があるためです。

辞書順最小のトポロジカル順序

キューの代わりに最小ヒープを使った Kahn法では、辞書順最小のトポロジカル順序が得られます。deque を heapq に置き換え、(node) を push し、常に利用可能なノードのうち最小のものを先に処理します。これにより、可能なすべてのトポロジカルソートの中で辞書順最小の有効な順序が保証されます。

import heapq
from collections import defaultdict

def kahn_lex_order(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    heap = [i for i in range(n) if in_degree[i] == 0]
    heapq.heapify(heap)
    order = []
    
    while heap:
        node = heapq.heappop(heap)
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                heapq.heappush(heap, nxt)
    
    return order if len(order) == n else []

print(kahn_lex_order(6, [(5,2),(5,0),(4,0),(4,1),(2,3),(3,1)]))

応用：Course Schedule I

Course Schedule (LeetCode 207) は、n 個のコースと前提条件が与えられたとき、すべてのコースを修了できるかを判定する問題です。前提条件を有向辺としてモデル化し、有効なトポロジカルソートが存在するか（つまり閉路がないか）を確認します。Kahn法による順序の長さが n なら True、閉路が検出されたら False を返します。

from collections import deque, defaultdict

def canFinish(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:   # b must be taken before a
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    count = 0
    while queue:
        node = queue.popleft()
        count += 1
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return count == numCourses

print(canFinish(2, [[1,0]]))       # True
print(canFinish(2, [[1,0],[0,1]])) # False (cycle)

応用：Course Schedule II

Course Schedule II (LeetCode 210) は、コースを履修する実際の順序を返す問題です。上記と同じですが、真偽値ではなく order リストを返します。閉路が存在する場合は、空のリストを返します。Kahn法の出力をそのまま答えとして利用できます。

from collections import deque, defaultdict

def findOrder(numCourses, prerequisites):
    graph = defaultdict(list)
    in_degree = [0] * numCourses
    for a, b in prerequisites:
        graph[b].append(a)
        in_degree[a] += 1
    
    queue = deque(i for i in range(numCourses) if in_degree[i] == 0)
    order = []
    while queue:
        node = queue.popleft()
        order.append(node)
        for nxt in graph[node]:
            in_degree[nxt] -= 1
            if in_degree[nxt] == 0:
                queue.append(nxt)
    
    return order if len(order) == numCourses else []

print(findOrder(4, [[1,0],[2,0],[3,1],[3,2]]))

並列タスクスケジューリング

より高度な応用として、依存関係のあるタスクについて、依存関係のないタスクを並列実行できる場合に必要な最小の「ラウンド」数を求める問題があります。BFS のレベル順探索と同様に、Kahn法をレベルごとに処理します。入次数が 0 のすべてのノードをキューに追加し、現在のキュー全体を1ラウンドとして処理し、その結果新たに処理可能になったノードを次のラウンドとして追加します。最後にラウンド数を数えます。

from collections import deque, defaultdict

def min_rounds(n, edges):
    graph = defaultdict(list)
    in_degree = [0] * n
    for u, v in edges:
        graph[u].append(v)
        in_degree[v] += 1
    
    queue = deque(i for i in range(n) if in_degree[i] == 0)
    rounds = 0
    while queue:
        rounds += 1
        for _ in range(len(queue)):  # process current level
            node = queue.popleft()
            for nxt in graph[node]:
                in_degree[nxt] -= 1
                if in_degree[nxt] == 0:
                    queue.append(nxt)
    return rounds

print(min_rounds(4, [(0,2),(1,2),(2,3)]))  # 3

DAGにおけるトポロジカルソートとDP

トポロジカルソートによって、DAG 上で動的計画法を利用できます。ノードをトポロジカル順に処理すると、dp[v] を計算する時点で、すべての先行ノードの dp[u] がすでに確定しています。これは、DAG 上の最長経路、すべてのノードに到達する最小コスト、依存関係の連鎖から得られる最大利益などの問題で、トポロジカルソートと DP を組み合わせる方法です。この順序により、各ノードの DP 値は、すべての依存関係の処理後にちょうど1回だけ計算されます。

from collections import deque, defaultdict

def longest_path_dag(V, edges):
    graph = defaultdict(list)
    in_degree = [0] * V
    for u, v, w in edges:
        graph[u].append((v, w))
        in_degree[v] += 1
    queue = deque(i for i in range(V) if in_degree[i] == 0)
    dp = [0] * V
    while queue:
        u = queue.popleft()
        for v, w in graph[u]:
            dp[v] = max(dp[v], dp[u] + w)
            in_degree[v] -= 1
            if in_degree[v] == 0: queue.append(v)
    return max(dp)

print(longest_path_dag(4, [(0,1,3),(0,2,2),(1,3,4),(2,3,1)]))  # 7

理解度チェック

このレッスンの Data Structures & Algorithms — Coding Interview Prep の概念について、理解度を確認しましょう。

レッスンのまとめ

このレッスンでは、Kahn法は入次数が 0 のノードを BFS で繰り返し削除することでトポロジカルソートを計算すること、閉路検出は追加の処理なしで行え、len(order) < n なら閉路が存在すること、そしてキューを最小ヒープに置き換えると辞書順最小のトポロジカル順序が得られることを学びました。次は、Kahn法の代替手法として、DFS に基づく帰りがけ順のトポロジカルソートを扱います。

よくある質問