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 の無向グラフが与えられる。グラフが何個の連結成分に分かれているかを数えよ。

参考： ABC284 C - Count Connected Components

回答　

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. 迷路全探索（すべての経路長を探索）

問題:
スタートからゴールまで、移動可能なルートのうち最大の長さを求めよ。

参考： ABC054 C - One-stroke Path

回答　

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)