DFS（深さ優先探索）でサイクル検出を考える【python実装】

有効サイクルとは

有効サイクルとは、下の図のように、例えばノード 0 から開始し、0 → 1 → 2 → 1 → 2 → 1 … というように 1 と 2 を何度も繰り返し周回するような有向グラフの形です。

サイクル検出 - 発想１

サイクルを検出するために、次のような手順を踏むことができます。

1. グラフをDFS（深さ優先探索）で探索（ノードのスタート地点は、for文を使って、0からnまでを全探索する）
2. 訪れたノードを記録する（visited[crr] = Trueなどとしておく）
3. 次の行き先ノードで、すでに訪れていれば（visited[nxt] = True）、サイクルと判定します。

この手順を踏めば、大体うまく行きそうです。

コードのざっくりとしたイメージ

cycle = False
def dfs(g, crr, visited):
    visited[crr] = True 
    for nxt in g[crr]:
        if not visited[nxt]:
            dfs(g, nxt, visited)
        else:
			global cycle
            cycle = True 

for crr in range(n):
    if not visited[crr]:
        dfs(g, crr, visited)

ちなみに無向グラフのときは、この考え方でほぼうまく行きます。

発想１で具体例を見る

発想１の方法で、例えば以下の「ケース１」を見ると、ノード０からスタートして
０→１→２→１(２回目なのでサイクル)

といった具合にサイクルを判定できます。
サイクルなしの「ケース２」でも、
０→１→２

という流れになります。
しかし「ケース３」ではうまく行きません。
「ケース２」と似ていますが、ノード番号の順番が違います。
０→ ２、1 → 0（２回目なのでサイクル？？？）

まず、ノード０からの探索をします。0→２で一度探索を終え、次はfor文により、ノード１から再び探索を始めます。しかし、1→０で２度目のノード０へ来るので、サイクルありの判定になってしまいます。

すでに探索済みのノードに到達した場合、それ以降のノードは探索しないとしたいですが、「探索済みのノードへ行こうとしたらサイクルあり」という条件を設定しているため、「ケース3」のように探索順序によって問題が発生する可能性があります。

問題点

この発想１の問題点は、(訪れた or 訪れていない)のフラグだけでは

• サイクル時の２回目の訪れ
• 探索順序による２回目の訪れ

を区別できないことです。

なので

• 成功例の「ケース１」ではON
• 失敗例の「ケース３」ではOFF

になるようなフラグが必要です。
そうすれば、２つのケースを区別できます。

サイクル検出 - 発想２

発想１に、次の新たな要素を加えます。

1. グラフをDFS（深さ優先探索）で探索（ノードのスタート地点は、for文を使って、0からnまでを全探索する）
2. 行き掛け順に、訪れたノードを記録する（visited[crr] = Trueとかしておく）
3. 帰り掛け順に、訪れたノードを記録する（finished[crr] = Trueとかしておく）new
4. 次の行き先ノードの内、visited[nxt] = True かつ finished[nxt] = Falseとなるようなノードがあれば、サイクルと判定

DFS（深さ優先探索）は、探索の行きと帰りがあります。それぞれについて、行きにはvisitedという配列、帰りにはfinishedという配列で、ノードに訪れたことを記録します。

行き掛け順、帰り掛け順という言葉がよくわからない人は、ここなど参考にしてみてください。

cycle = True
def dfs(g, crr, visited):
    visited[crr] = True # 行き掛け順の記録
    for nxt in g[crr]:
        if not visited[nxt]:
            dfs(g, nxt, visited)
        elif not finished[nxt]: # new
			global cycle
            cycle = True
    finished[crr] = True # new　帰り掛け順の記録

for crr in range(n):
    if not visited[crr]:
        dfs(g, crr, visited)

発想２で具体例を見る

「ケース１」を発想２で考えます。

まず、行き掛け順に0→1→2→1(2回目）と探索します。２回目のノード１へ来たとき、visited[1] = True 、finished[1] = Falseなので、サイクルありの判定になります。
行き掛け順の後は、帰り掛け順にfinishedを1→2→1→0の順にTrueにします。

「ケース３」も考えてみましょう。

まず、ノード０からスタートして、行き掛け順に０→２と探索します。このとき、visited[0], visited[2]を順にTrueにします。それから、帰りがけ順に２→０と戻り、finished[2], finished[0]を順にTrueにします。
これで一旦探索を終え、今度はノード１からスタート。
１→０の順に探索をします。このとき、ノード０は一度訪れているのでvisited[0] = Trueですが、finishd[0] = True（もうすでに探索済み）なので、サイクルありの判定を無視します。

結果としてサイクルなしと判定し、うまく行きます。

全コード

アルゴ式の問題「Q8. サイクル検出 (D)」対応したコードです。

import sys
sys.setrecursionlimit(10**4)

n, m = map(int, input().split())
g = [[] for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    g[u].append(v)

cycle = False
def dfs(g, crr, visited, finished):
    visited[crr] = True
    for nxt in g[crr]:
        if not visited[nxt]:
            dfs(g, nxt, visited, finished)
        elif not finished[nxt]:
            global cycle
            cycle = True
    finished[crr] = True

visited = [False] * n
finished = [False] * n
for crr in range(n):
    if not visited[crr]:
        dfs(g, crr, visited, finished)

print("Yes" if cycle else "No")