《アルゴリズムを学ぶ》25.深さ優先探索（DFS）

# Overview
DFS（Depth-First Search） は、「できるだけ深く探索してから戻る」 グラフ探索アルゴリズム。
[1.深さ優先探索の基本](#1-深さ優先探索の基本)
[2.深さ優先探索の応用例](#2-深さ優先探索の応用例)
[3.典型問題を解いてみる](#3-典型問題を解いてみる)

# 1. 深さ優先探索の基本
スタック（再帰）または明示的な `stack` を用いて、再帰的な探索や経路の列挙などに用いられる。

### (1) 基本実装１：再帰版 DFS（隣接リスト）
「ある頂点からスタートして、行けるところまでどんどん奥へ進む」という処理。
イメージとしては、「一本道を進めるだけ進んで、行き止まりになったら戻る」という動きを繰り返す。
```python
def dfs(v):
    visited[v] = True        #①ノードvを訪問済みとして記録
    for nv in graph[v]:      #②ノードvの隣接ノードを順に調べる
        if not visited[nv]:  #③未訪問のノードがあれば、再帰的にそこへ進む
            dfs(nv)          #④新しいノードに進み、さらに探索を続ける
```
**<例>**
下記のような無向グラフを探索する場合。
```
0 -- 1 -- 3
|         |
2---------
```
隣接リスト(graph)は下記の通りになる。
```Python
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: 辺数）
```python
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のコードテンプレ（無向グラフ・再帰版）
```Python
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](https://atcoder.jp/contests/abc284/tasks/abc284_c)
<details><summary> 回答　</summary>

```python
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)
```
</details>

### 例題2. 迷路全探索（すべての経路長を探索）
**問題:
スタートからゴールまで、移動可能なルートのうち最大の長さを求めよ。**

> [参考： ABC054 C - One-stroke Path](https://atcoder.jp/contests/abc054/tasks/abc054_c)
<details><summary> 回答　</summary>

```python
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)
```
</details>