0Pricing
Coding Interview Prep · レッスン

有向グラフのサイクル検出

ノードを色付けして後退辺を見つけます

「有向グラフのサイクル検出」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

閉路が重要な理由

有向閉路があると、依存関係が互いを参照し続けます。閉路を見つければ、トポロジカル順序も有効なスケジュールも存在しないと分かります。

無向グラフとは異なる

ここでの閉路検出では向きが重要です。辺を逆方向にたどることは数えないため、無向グラフの方法は使えません。

3色で管理する考え方

各ノードに3色のいずれかを割り当てます。白は未訪問、灰色は処理中、黒は処理完了を表します。

WHITE, GRAY, BLACK = 0, 1, 2
color = [WHITE] * n

灰色はスタック上を表す

灰色のノードは、現在のDFSパス上にあります。そのノードには到達済みですが、すべての子孫の探索はまだ終わっていません。

ノードに入る

DFSでノードに到達したら、探索する前に灰色にします。これにより、そのノードが現在の経路に含まれることを記録します。

def dfs(u):
    color[u] = GRAY

後退辺の合図

すでに灰色の隣接ノードに到達したら、現在の経路へ戻る後退辺を見つけたことになります。これは閉路です。

for v in adj[u]:
    if color[v] == GRAY:
        return True  # cycle

白いノードへ再帰する

白の隣接ノードは未探索なので、そこへ再帰します。深い呼び出しのいずれかが閉路を報告したら、すぐに True を上へ返します。

    elif color[v] == WHITE and dfs(v):
        return True

黒なら安全

黒の隣接ノードは探索済みで、閉路もないため無視できます。もう一度たどっても時間を無駄にするだけです。

ノードの処理を終える

すべての隣接ノードを処理したら、そのノードを黒にします。これで現在の経路から離れ、処理完了として記録されます。

    color[u] = BLACK
    return False

すべての連結成分を調べる

グラフは非連結の場合があるため、まだ白いノードすべてを始点にしてDFSを開始し、全体を確実に調べます。

if any(color[u]==WHITE and dfs(u) for u in range(n)):
    print('cycle')

再帰の上限に注意する

深いグラフでは、Pythonの再帰スタックがあふれることがあります。上限を引き上げるか、明示的なスタックを使うDFSに書き換えてください。

import sys
sys.setrecursionlimit(300000)

理解度チェック

DFS中に、現在灰色になっている隣接ノードへ到達しました。何を見つけたことになりますか？

まとめ: 閉路検出

ノードを白、灰色、黒の順に色付けします。DFS中に灰色の隣接ノードがあれば、それは後退辺であり、有向閉路の存在が証明されます。🔁

よくある質問

「有向グラフのサイクル検出」レッスンは無料ですか？

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

「有向グラフのサイクル検出」で何を学びますか？

ノードを色付けして後退辺を見つけます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「有向グラフのサイクル検出」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

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