0Pricing
Competitive Programming Academy · レッスン

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

他のタスクに依存するタスクを順序付けます

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

トポロジカル順序とは

トポロジカル順序とは、有向グラフのすべてのノードを並べ、各辺が前のノードから後のノードへ向くようにした順序です。先に実行すべきタスクを、依存するタスクより前に置くと考えてください。

DAGだけが対象

これはDAG（有向非巡回グラフ）でのみ機能します。閉路があると、すべての依存関係を満たす有効な順序は存在しません。

入次数の考え方

Kahnのアルゴリズムは入次数、つまりあるノードに向かって入る辺の本数を利用します。入次数が0のノードには、未解決の依存関係がありません。

すべての入次数を数える

最初の処理では、すべての辺をたどり、各ノードが何回終点になっているかを数えます。これで各ノードの入次数が得られます。

indeg = [0] * n
for u in range(n):
    for v in adj[u]:
        indeg[v] += 1

準備完了キューを初期化する

入次数が0のノードはすぐに処理できるため、最初にすべてキューへ入れます。

from collections import deque
q = deque(u for u in range(n) if indeg[u] == 0)

1つのノードを処理する

処理可能なノードを1つ取り出し、順序に追加します。残りの依存関係がないため、この時点で安全に処理できます。

u = q.popleft()
order.append(u)

隣接ノードを解放する

各隣接ノードの入次数を1つ減らします。隣接ノードの入次数が0になったら、処理可能になったのでキューへ追加します。

for v in adj[u]:
    indeg[v] -= 1
    if indeg[v] == 0:
        q.append(v)

空になるまで繰り返す

キューが空になるまで、ノードの取り出しと隣接ノードの解放を続けます。安全に処理できるノードを1つずつ置いていくことで、すべてのノードが順序に追加されます。

追加コストなしで閉路を検出する

最終的な順序に n 個未満のノードしか含まれていなければ、残りのノードは閉路に閉じ込められています。Kahnのアルゴリズムなら、追加コストなしで閉路も検出できます。

if len(order) < n:
    print('cycle exists')

計算量

各ノードと各辺を1回ずつ処理するため、Kahnのアルゴリズムの計算量はO(V + E)です。辺が数百万本あるグラフにも対応できます。

有効な順序は複数ある

複数のノードが同時に処理可能な場合、どれを次に選んでも構いません。そのため、DAGには有効なトポロジカル順序が1つだけでなく多数存在することがよくあります。

理解度チェック

Kahnのアルゴリズムを終えたところ、順序に含まれるノードが n 個未満でした。これは何を意味しますか？

まとめ: Kahnのアルゴリズム

入次数を数え、0のノードをキューに入れ、ノードを取り出し、隣接ノードの入次数を減らして、これを繰り返します。これが O(V+E) のトポロジカルソートです。🚀

よくある質問

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

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

「Kahn のアルゴリズムによるトポロジカルソート」で何を学びますか？

他のタスクに依存するタスクを順序付けます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

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

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

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

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

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

このコースのすべてのレッスン

  1. Kahn のアルゴリズムによるトポロジカルソート
  2. 有向グラフのサイクル検出
  3. 強連結成分
  4. 橋と関節点
← Competitive Programming Academyに戻る