グラフにおけるサイクル検出

グラフのサイクルを検出することは、依存関係の管理、デッドロック検出、ネットワークのルーティングなど、さまざまな分野でデータの構造や特性を理解するうえで非常に重要です。サイクルを特定することで、循環依存、非効率性、さらにはシステム障害といった問題を未然に防ぐことができます。

グラフ内のサイクルを検出するには、通常の DFS を少し改変した方法を使うことができます。

DFS を使ってグラフを探索する際、通常は頂点を「訪問済み」または「未訪問」のどちらかで管理します。しかしサイクルを検出するにはこれでは不十分です。各頂点に対して以下の 3 つの状態を保持する必要があります:

頂点が未訪問である

頂点とその DFS サブツリーを処理中である

頂点が完全に訪問済み（すべての子ノードも含め）である

こうすることで、探索中に「処理中」の頂点に再度到達した場合、その頂点を含むサイクルが存在すると判断できます。

➰

グラフを辿っている最中に、状態 (2) の頂点に到達した場合は、サイクルがあると判断できます。

このアルゴリズムは以下の手順で実行されます:

すべての頂点を未訪問にマークする

任意の頂点から DFS を開始する

現在の頂点を処理中としてマークする

現在の頂点のすべての子ノードの処理が終わったら、その頂点を完全に訪問済みにマークする

このアルゴリズムは、有向グラフと無向グラフの両方に適用可能です:

color = [1] * n                             # 頂点の色 (1: 未訪問、2: 処理中、3: 処理完了)

def dfs(v, p):                              # 深さ優先探索 (v: 頂点, p: 親)
    color[v] = 2                            # 頂点を処理中にマーク
    cycle = False                           # サイクルがあるかどうかを示すフラグ

    for to in g[v]:                         # v に隣接する頂点に対して
        if color[to] == 1:                  # 頂点が未訪問の場合
            cycle |= dfs(to, v)             # dfs を呼び出し、サイクルが発見されたかどうかを記録
        elif color[to] == 2 and to != p:    # 頂点が処理中で、かつそれが親でないなら
            cycle = True                    # フラグを True にする
    color[v] = 3                            # 頂点を完全に訪問済みにマーク
    return cycle                            # フラグを返す


for start in range(n):                      # すべての頂点に対して
    if color[start] == 1:                   # 頂点が未訪問なら
        if dfs(start, -1):                  # 頂点に対して dfs を呼び、サイクルがあるかどうかをチェック
            print('Cycle')                  # サイクルがある場合に表示
            break                           # ループを中断
else:                                       # break で中断されなかった場合
    print('No cycle')                       # サイクルなしを表示

有向グラフの場合は、親頂点を考慮する必要がないことに注意してください。なぜでしょうか？🤔

いくつかの入力例を使って、このアルゴリズムをシミュレーションしてみましょう:

n = 4, e = 4

入力 a, b の組は以下のとおりです: [(0, 1), (0, 2), (1, 2), (3, 2)]

開始頂点は 3 です

v=3, p=-1 → color = [1, 1, 1, 2] ⇒ 3 のすべての隣接頂点を探索 ⇒ [2]

v=2, p=3 → color = [1, 1, 2, 2] ⇒ 2 のすべての隣接頂点を探索 ⇒ [0, 1]

v=0, p=2 → color = [2, 1, 2, 2] ⇒ 0 のすべての隣接頂点を探索 ⇒ [1, 2]

v=1, p=0 → color = [2, 2, 2, 2] ⇒ 1 のすべての隣接頂点を探索 ⇒ [0, 2] ⇒ 0 は状態 1 のため cycle = True をマーク ⇒ return True

チャレンジ: グラフ内にサイクルが存在するかを判定する

有向グラフで、頂点数を表す v と、辺の数を表す e が与えられたとき、このグラフにサイクルがあるかどうかを判定してください。

入力

最初の行に v (1 ≤ v ≤ 100 000) と e (1 ≤ e ≤ 100 000) の 2 つの整数が与えられます。

続く e 行には、2 つの整数 v1, v2 (1 ≤ v1, v2 ≤ v) が与えられ、これは頂点 v1 から頂点 v2 へパスが存在することを意味します。

出力

もしグラフにサイクルが存在すれば Yes、そうでなければ No を出力してください。

例

Input	Output
4 3 1 2 2 3 3 1	Yes
4 3 1 2 1 3 2 4	No

チャレンジ: グラフ内にサイクルが存在するかを判定する

入力

出力

例

Constraints

To check your solution you need to sign in

Sign in to continue