Overview
DFS（Depth-First Search） は、「できるだけ深く探索してから戻る」 グラフ探索アルゴリズム。
1.深さ優先探索の基本
2.深さ優先探索の応用例
3.典型問題を解いてみる
1. 深さ優先探索の基本
スタック（再帰）または明示的な stack を用いて、再帰的な探索や経路の列挙などに用いられる。
(1) 基本実装１：再帰版 DFS（隣接リスト）
「ある頂点からスタートして、行けるところまでどんどん奥へ進む」という処理。
イメージとしては、「一本道を進めるだけ進んで、行き止まりになったら戻る」という動きを繰り返す。
def dfs(v):
visited[v] = True #①ノードvを訪問済みとして記録
for nv in graph[v]: #②ノードvの隣接ノードを順に調べる
if not visited[nv]: #③未訪問のノードがあれば、再帰的にそこへ進む
dfs(nv) #④新しいノードに進み、さらに探索を続ける
<例>
下記のような無向グラフを探索する場合。
0 -- 1 -- 3
| |
2---------
隣接リスト(graph)は下記の通りになる。
graph = [
[1, 2], # 0
[0, 3], # 1
[0, 3], # 2
[1, 2] # 3
]
DFS(0) を呼び出すと、処理イメージは下記の通り。
処理1.（①にて）visited[0] = True（0は訪問済で記録）
処理2.（②③にて）graph[0] = [1, 2] → 最初の未訪問隣接ノード 1に行く(nv = 1)
処理3.（④にて）dfs(1) が呼ばれ、（①にて）visited[1] = True（1は訪問済で記録）
処理4.（②にて）graph[1] = [0, 3] → （nv = 0として、③にて）0 は訪問済みと判定、次に 3 に行く(nv = 3)
処理5.（④にて）dfs(3) が呼ばれ、visited[3] = True（3は訪問済で記録）
処理6.（②にて）graph[3] = [1, 2] → （nv = 1として、③にて）1 は訪問済み、2 に行く(nv = 2)
処理7.（④にて）dfs(2) が呼ばれ、visited[2] = True（2は訪問済で記録）
処理8.（②にて）graph[2] = [0, 3] → どちらも訪問済み → 戻る
処理9.これで 3 （処理５）に戻り、次の隣接ノードは済み → 戻る
処理10.これで 1 （処理３）に戻り、次の隣接ノードは済み → 戻る
処理11.最初の dfs(0) に戻り、2 は既に訪問済み → 完了
(2)スタック版 DFS（明示的なstack使用）
「訪問すべきノードを明示的なスタックに積んでおき、後から取り出して深く探索する」という処理。Python の関数呼び出しスタックを使わず、自分でstackを使って管理する方法です。
計算量：O(V + E)（V: 頂点数, E: 辺数）
def dfs_stack(start):
stack = [start] #①探索の開始点を stack に入れる
visited[start] = True
while stack: #②探索すべきノードがある限り続ける
v = stack.pop() #③一番上のノードを取り出して探索
for nv in graph[v]: #④隣接するノードを確認
if not visited[nv]: #⑤未訪問なら訪問してスタックに追加
visited[nv] = True #⑥
stack.append(nv) #⑦
<例>
再帰版と同じグラフを探索する場合...
dfs_stack(0)を呼び出すと、処理イメージは下記の通り。
処理1.stack = [0](①のロジック）、visited[0] = True（0は訪問済で記録）
処理2.v = 0 を pop（③のロジック） → graph[0] = [1, 2]
処理3.（⑥⑦のロジックにて）visited[1] = True, stack に追加 → stack = [1]
処理4.（⑥⑦のロジックにて）visited[2] = True, stack に追加 → stack = [1, 2]
処理5.（後入れ先出しなので）v = 2 を pop（③のロジック） → graph[2] = [0, 3]
処理6.（⑤⑥⑦のロジックにて）0 は訪問済み、3 は未訪問 → visited[3] = True, stack = [1, 3]
処理7.v = 3 を pop → graph[3] = [1, 2] → どちらも訪問済み → 終了
処理8.v = 1 を pop → graph[1] = [0, 3] → どちらも訪問済み → 終了
処理9.stack 空 → 探索終了
(3)再帰版とスタック版 の違い
| 比較項目 | 再帰版 DFS | スタック版 DFS |
|---|---|---|
| 管理 | Python の呼び出しスタックに任せる | 自分で stack を使って管理 |
| 安全性 | 再帰が深すぎると RecursionError | 再帰制限を回避できる |
| 実装の自由度 | 書きやすいが制御しにくいことも | スタックを細かく制御できる |
| 教育的観点 | DFS の本質がわかりやすい | 実行の流れを「見える化」できる |
スタック版は下記のようなときに使われる。
- 再帰の深さが 1000 を超える可能性があるとき（Python の再帰制限に引っかかる）
- 明示的に探索の順番を管理したいとき
- 競技プログラミングや本番環境でスタックオーバーフローを避けたいとき
(4)DFSのコードテンプレ（無向グラフ・再帰版）
import sys
sys.setrecursionlimit(10**6)
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
a, b = map(int, input().split())
graph[a].append(b)
graph[b].append(a)
visited = [False] * N
def dfs(v):
visited[v] = True
for nv in graph[v]:
if not visited[nv]:
dfs(nv)
# 0 からスタート
dfs(0)
2. 深さ優先探索の応用例
| 応用例 | 説明 |
|---|---|
| 連結成分の個数を数える | グラフを何個のまとまりに分けられるか |
| 閉路（サイクル）検出 | 再帰中に「既に訪問したノード」に戻るとサイクルがある |
| 迷路全探索 | スタートからゴールへのすべての経路を探す |
| 経路復元 | prev[] を使って通ったルートを記録する |
3. 典型問題を解いてみる
例題1. 無向グラフの連結成分を数える
問題:
頂点数 N、辺数 M の無向グラフが与えられる。グラフが何個の連結成分に分かれているかを数えよ。
回答
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
u, v = map(lambda x: int(x)-1, input().split())
graph[u].append(v)
graph[v].append(u)
visited = [False] * N
def dfs(v):
visited[v] = True
for nv in graph[v]:
if not visited[nv]:
dfs(nv)
count = 0
for i in range(N):
if not visited[i]:
dfs(i)
count += 1
print(count)
例題2. 迷路全探索（すべての経路長を探索）
問題:
スタートからゴールまで、移動可能なルートのうち最大の長さを求めよ。
回答
from itertools import permutations
N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
a, b = map(lambda x: int(x)-1, input().split())
graph[a].append(b)
graph[b].append(a)
count = 0
for perm in permutations(range(N)):
valid = True
for i in range(N-1):
if perm[i+1] not in graph[perm[i]]:
valid = False
break
if valid:
count += 1
print(count)