深さ優先探索(DFS)とは何か?

Question

深さ優先探索(DFS)とは何か?

Accepted Answer

**DFS** は、グラフを各分岐に沿って可能な限り深く進んでからバックトラックすることで探索します。**スタック**(多くの場合は再帰による呼び出しスタック)を使用し、完全なパスを訪れてから別の分岐を探索します。

## アイデア

ノードから未訪問の隣接ノードに再帰し、深く進み続けます。行き止まりになったら戻って別の分岐を試します。

## 例

```python
def dfs(graph, node, visited=None):
    if visited is None:
        visited = set()
    visited.add(node)
    order = [node]
    for nbr in graph[node]:
        if nbr not in visited:
            order += dfs(graph, nbr, visited)  # go deeper first
    return order

graph = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}
dfs(graph, 'A')                        # -> ['A', 'B', 'D', 'C']
```

## BFS vs DFS

| | BFS | DFS |
|---|-----|-----|
| データ構造 | キュー | スタック / 再帰 |
| 探索内容 | 最短経路(無加重) | 任意のパス |
| メモリ | O(V) フロンティア | O(深さ) |
| 用途 | 最短経路、レベル | サイクル検出、トポロジカルソート、連結成分 |

## 計算量

- **時間:** O(V + E)。**空間:** O(V)(再帰深度 + 訪問済み)。

## 落とし穴

深いグラフは再帰スタックをオーバーフローさせる可能性があります。明示的なスタックを使用してください。`visited` を追跡してサイクルを処理します。

## なぜ重要なのか

DFS はサイクル検出、トポロジカルソート、連結成分、迷路/パス生成の基礎です。

その再帰的な優雅さは、ツリーとグラフのコードを簡潔にします。

深さ優先がどのような場合に幅優先を上回るかを知ることは、グラフアルゴリズム流暢性の核心です。

	BFS	DFS
データ構造	キュー	スタック / 再帰
探索内容	最短経路(無加重)	任意のパス
メモリ	O(V) フロンティア	O(深さ)
用途	最短経路、レベル	サイクル検出、トポロジカルソート、連結成分