有向・無向グラフの循環検出
無向グラフでは親を追跡して、有向グラフではDFSの色付け（白・灰・黒の3状態の訪問管理）を使って循環を検出します。
「有向・無向グラフの循環検出」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。
サイクル検出が重要な理由
グラフにおけるサイクルとは、同じノードから始まり、そのノードに戻ってくる経路です。サイクル検出は多くのアルゴリズムで重要です。サイクルを含むグラフではトポロジカルソートが失敗し、依存関係の解決では循環依存を検出する必要があり、OSのスケジューリングにおけるデッドロック検出ではリソース割り当てグラフのサイクルを見つける必要があります。無向グラフと有向グラフではアプローチが異なり、それぞれ根本的に異なるアルゴリズムが必要です。
from collections import defaultdict
# Undirected cycle: A-B-C-A (triangle)
undirected = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
undirected[u].append(v)
undirected[v].append(u)
# Directed cycle: A->B->C->A
directed = defaultdict(list)
for u, v in [('A','B'),('B','C'),('C','A')]:
directed[u].append(v) # one direction only
# Key difference:
# Undirected: edge A-B appears as both A->B and B->A
# Must track parent to distinguish cycle from back-edge to parent
print('Undirected and directed cycles need different detection')DFSによる無向グラフのサイクル検出
無向グラフでは、DFSが現在の経路上にある（単に訪問済みであるだけではない）ノードを訪問すると、サイクルが存在します。難しい点は、すべての辺が両方向に現れることです。そのため、子ノードを訪問すると、その隣接ノードの一覧には現在のノード（親）も含まれます。親への辺をサイクルと誤判定しないように、各ノードの親を追跡する必要があります。訪問済みで、かつ自分の親ではないノードに遭遇した場合、サイクルが見つかったことになります。
def has_cycle_undirected(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
def dfs(node, parent):
visited.add(node)
for nb in graph[node]:
if nb not in visited:
if dfs(nb, node): # recurse with current as parent
return True
elif nb != parent: # visited and not parent = CYCLE
return True
return False
for node in range(n):
if node not in visited:
if dfs(node, -1): # -1 = no parent for root
return True
return False
print(has_cycle_undirected(4, [(0,1),(1,2),(2,3),(3,1)])) # True
print(has_cycle_undirected(3, [(0,1),(1,2)])) # FalseBFSによる無向グラフのサイクル検出
無向グラフでBFSによってサイクルを検出する場合も、訪問済みの各ノードの親を追跡します。あるノードの隣接ノードを処理するとき、隣接ノードがすでに訪問済みで、現在のノードの親でなければ、サイクルが存在します。親を格納するには辞書を使用します。このO(V + E)の方法は再帰上限の問題を避けられるため、大規模なグラフに対する反復処理の方法として推奨されます。
from collections import deque, defaultdict
def has_cycle_bfs_undirected(n, edges):
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = set()
for start in range(n):
if start in visited:
continue
visited.add(start)
parent = {start: -1}
queue = deque([start])
while queue:
node = queue.popleft()
for nb in graph[node]:
if nb not in visited:
visited.add(nb)
parent[nb] = node
queue.append(nb)
elif parent[node] != nb: # visited and not parent = CYCLE
return True
return False
print(has_cycle_bfs_undirected(4, [(0,1),(1,2),(2,0)])) # True有向グラフのサイクル：親の追跡では不十分な理由
有向グラフでは、親を追跡するだけでは不十分です。A→CとB→Cを考えてみましょう。ノードCには2つの「親」がありますが、サイクルはありません。正しいアプローチでは3状態の色分けを使います。白（未訪問）、灰（現在のDFS経路／スタック内）、黒（完全に処理済み）です。DFS中に灰のノードに遭遇した場合、サイクルが存在します。これは、現在の経路にある祖先への後退辺が見つかったことを意味します。
# Three-state DFS coloring:
# WHITE (0): not yet visited
# GRAY (1): currently being visited (in DFS stack)
# BLACK (2): fully visited (all descendants processed)
# Why parent fails for directed graphs:
# A -> C (no cycle)
# B -> C (no cycle)
# If we DFS from A, mark C gray
# Then DFS from B finds C is gray -- but this is NOT a cycle!
# C is gray from A's path, not B's path.
# Parent tracking only works when the back-edge goes to the IMMEDIATE parent.
print('Directed graph: use 3-state coloring (white/gray/black)')3状態DFSによる有向グラフのサイクル検出
値として0（白／未訪問）、1（灰／スタック内）、2（黒／完了）を持つ配列state[]を使用します。DFSを開始し、ノードに入るときに灰、終了するときに黒としてマークします。DFSが灰のノードに到達した場合、後退辺が見つかったことになり、サイクルが存在します。黒のノードに到達した場合、その経路はすでに完全に探索されておりサイクルがないため、スキップします。
def has_cycle_directed(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n # 0=white, 1=gray, 2=black
def dfs(node):
state[node] = 1 # mark gray (in stack)
for nb in graph[node]:
if state[nb] == 1: # gray = back edge = CYCLE
return True
if state[nb] == 0: # white = unvisited
if dfs(nb):
return True
state[node] = 2 # mark black (fully processed)
return False
for node in range(n):
if state[node] == 0:
if dfs(node):
return True
return False
print(has_cycle_directed(4, [(0,1),(1,2),(2,0),(2,3)])) # True (0->1->2->0)
print(has_cycle_directed(3, [(0,1),(1,2)])) # Falseコーススケジュール：DAG内のサイクル
コーススケジュール（LeetCode #207）は、前提条件が与えられたときにすべてのコースを修了できるかを問う問題です。コースをノード、前提条件を有向辺としてモデル化します。すべてのコースを修了できるのは、グラフがDAG（サイクルのない有向非巡回グラフ）である場合、かつその場合に限ります。3状態DFSによるサイクル検出を使い、サイクルが見つかったらFalse、見つからなければTrueを返します。
from collections import defaultdict
def can_finish(num_courses, prerequisites):
graph = defaultdict(list)
for a, b in prerequisites:
graph[b].append(a) # b is prerequisite for a: b -> a
state = [0] * num_courses
def dfs(course):
if state[course] == 1: return False # cycle!
if state[course] == 2: return True # already verified
state[course] = 1 # mark as in-progress
for next_course in graph[course]:
if not dfs(next_course):
return False
state[course] = 2 # mark as done
return True
return all(dfs(i) for i in range(num_courses) if state[i] == 0)
print(can_finish(2, [[1,0]])) # True: take 0 then 1
print(can_finish(2, [[1,0],[0,1]])) # False: circular dependencyカーンのアルゴリズム（BFS）によるサイクル検出
有向グラフのサイクル検出には、カーンのBFSトポロジカルソートを使う別の方法もあります。すべてのノードの入次数を数えます。入次数が0のノードをキューに入れます。各ノードを処理し、その隣接ノードの入次数を減らして、0になったノードをキューに追加します。処理したノード数がVと等しければサイクルはなく、そうでなければサイクルが存在します（未処理のノードがサイクルを形成しています）。このO(V + E)の方法は直感的で、3状態DFSよりも覚えやすい方法です。
from collections import defaultdict, deque
def has_cycle_kahn(n, edges):
graph = defaultdict(list)
in_degree = [0] * n
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
# Start with all zero in-degree nodes
queue = deque(i for i in range(n) if in_degree[i] == 0)
processed = 0
while queue:
node = queue.popleft()
processed += 1
for nb in graph[node]:
in_degree[nb] -= 1
if in_degree[nb] == 0:
queue.append(nb)
return processed != n # if not all processed, cycle exists
print(has_cycle_kahn(4, [(0,1),(1,2),(2,0),(2,3)])) # True
print(has_cycle_kahn(3, [(0,1),(1,2)])) # Falseサイクルの特定：サイクルノードの収集
サイクルの存在を検出するだけでなく、どのノードがサイクルの一部であるかを特定する必要がある場合もあります。3状態DFSで後退辺が見つかったら、コールスタック（またはパススタック）をたどって、祖先から現在のノードまでのすべてのノードを収集します。state配列と並行してパススタックを管理すると、現在のDFS経路を取得でき、O(cycle_length)でサイクルを再構成できます。
def find_cycle_nodes(n, edges):
from collections import defaultdict
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
state = [0] * n
path = [] # current DFS path
cycle = []
def dfs(node):
state[node] = 1
path.append(node)
for nb in graph[node]:
if state[nb] == 1: # back edge -> found cycle
start = path.index(nb)
cycle.extend(path[start:])
return True
if state[nb] == 0 and dfs(nb):
return True
path.pop()
state[node] = 2
return False
for i in range(n):
if state[i] == 0 and dfs(i):
break
return cycle
print(find_cycle_nodes(4, [(0,1),(1,2),(2,0),(2,3)])) # [0, 1, 2]最終的に安全なノードを見つける
最終的に安全なノードを見つける（LeetCode #802）は、サイクルに陥ることなく最終ノード（出ていく辺を持たないノード）へ最終的に到達するノードを求める問題です。あるノードから始まるすべての経路が最終ノードへ到達する場合、そのノードは「安全」です。3状態DFSを使います。黒（サイクルを検出せずに完全に処理済み）のノードは安全です。サイクルの一部であるノードやサイクルへつながるノードは安全ではありません。
def eventual_safe_nodes(graph):
n = len(graph)
state = [0] * n # 0=unvisited, 1=visiting, 2=safe
def dfs(node):
if state[node] == 1: # currently visiting = cycle
return False
if state[node] == 2: # already verified safe
return True
state[node] = 1 # mark as visiting
for nb in graph[node]:
if not dfs(nb):
return False # leads to cycle, not safe
state[node] = 2 # mark as safe
return True
return [i for i in range(n) if dfs(i)]
# [[1,2],[2,3],[5],[0],[5],[],[]] means:
# 0->[1,2], 1->[2,3], 2->[5], 3->[0] (cycle!), 4->[5], 5->[], 6->[]
print(eventual_safe_nodes([[1,2],[2,3],[5],[0],[5],[],[]]))
# [2, 4, 5, 6]無向グラフの余分な辺
余分な辺（LeetCode #684）は、非巡回の無向グラフに辺を追加したときにサイクルを作る辺を見つける問題です。DFSによるサイクル検出でも解けますが、最も簡潔な解法はUnion-Find（DSU）を使う方法です。辺を1本ずつ処理し、両端点がすでに接続されている（同じ連結成分に属している）場合、現在の辺がサイクルを作るため、それが答えです。DSUでは1回の操作をO(alpha(n))で実行でき、実質的にO(1)です。
def find_redundant_connection(edges):
n = len(edges)
parent = list(range(n + 1))
rank = [0] * (n + 1)
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # path compression
return parent[x]
def union(x, y):
px, py = find(x), find(y)
if px == py:
return False # already connected = cycle!
if rank[px] < rank[py]: px, py = py, px
parent[py] = px
if rank[px] == rank[py]: rank[px] += 1
return True
for u, v in edges:
if not union(u, v):
return [u, v] # this edge creates the cycle
return []
print(find_redundant_connection([[1,2],[1,3],[2,3]])) # [2,3]
print(find_redundant_connection([[1,2],[2,3],[3,4],[1,4],[1,5]])) # [1,4]まとめ：サイクル検出の戦略
サイクル検出のツールキットをまとめます。無向グラフでは、親を追跡するDFSまたはUnion-Findを使います。有向グラフでは、3状態DFS（白／灰／黒）またはカーンのBFSトポロジカルソートを使います。辺を1本ずつ追加するオンライン処理ではUnion-Findを選びます。トポロジカル順序も必要な場合はカーンのアルゴリズムを選びます。特定のサイクルノードを特定する必要がある場合は、3状態DFSを選びます。面接でサイクル検出について説明するときは、必ず有向グラフと無向グラフの違いを明示してください。
# Cycle detection summary:
# Graph type | Algorithm | Complexity
# ------------|----------------------|-----------
# Undirected | DFS + parent track | O(V + E)
# Undirected | Union-Find (DSU) | O(E * alpha(V))
# Directed | DFS 3-state (W/G/B) | O(V + E)
# Directed | Kahn's BFS topo sort | O(V + E)
# When to choose:
# Online (edges added one at a time): Union-Find
# Need topological order too: Kahn's BFS
# Need cycle nodes identified: 3-state DFS with path stack
# Simple existence check: any of the above
print('Always clarify directed vs undirected before coding')理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、親の追跡を伴うDFSによる無向グラフのサイクル検出、白／灰／黒の3状態の色分けによる有向グラフのサイクル検出、有向グラフに対するカーンのBFSによる代替手法、さらにコーススケジュール、余分な辺、最終的に安全なノードといった応用を学びました。次は、動的計画法の基礎に進みます。
よくある質問
「有向・無向グラフの循環検出」レッスンは無料ですか？
はい。「有向・無向グラフの循環検出」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。
「有向・無向グラフの循環検出」で何を学びますか？
無向グラフでは親を追跡して、有向グラフではDFSの色付け（白・灰・黒の3状態の訪問管理）を使って循環を検出します。 ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Coding Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。
「有向・無向グラフの循環検出」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCoding Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- グラフ表現と走査の準備
- BFS：最短経路とレベル走査
- DFS：連結成分とflood fill
- 有向・無向グラフの循環検出