アルゴリズムやAIの分野で頻繁に登場する「探索」という考え方。
その中でも基本かつ重要な手法が「深さ優先探索（DFS）」です。
本記事では、DFSの仕組みや特徴、具体例、幅優先探索（BFS）との違いまで、初心者にもわかりやすく解説します。
深さ優先探索（DFS）とは
深さ優先探索（DFS）とは、できるだけ奥（深いノード）へ進んでから戻る探索アルゴリズムです。
グラフ構造や木構造のすべてのノードを訪れるために使われます。
DFSの基本的な考え方
DFSは次のような流れで進みます。
- スタート地点から探索開始
- 行けるところまで一直線に進む
- 行き止まり（末端）に到達
- 1つ前に戻る（バックトラック）
- まだ探索していない別ルートへ進む
- すべてのノードを訪れるまで繰り返す
このように「深く潜ってから戻る」動きが特徴です。
具体例で理解するDFS
例えば、以下のような木構造があるとします。
├─ B
│ ├─ D
│ └─ E
└─ C
└─ F
DFSの探索順は次のようになります。
- A → B → D（ここで行き止まり）
- Bに戻る → E
- Aに戻る → C → F
つまり、「とにかく奥まで進む」動きになります。
スタック構造とDFS
DFSでは、探索の順番を管理するためにスタックというデータ構造がよく使われます。
スタックとは
- 後から入れたものを先に取り出す（LIFO）
- Last-In First-Out（後入れ先出し）
この性質がDFSと相性が良く、探索の流れを効率的に管理できます。
再帰処理による実装
DFSは、プログラムでは「再帰処理」で簡潔に書けることが多いです。
- 関数が自分自身を呼び出す
- 自然に「深く進む→戻る」動きになる
そのため、アルゴリズム学習の初期段階でよく登場します。
DFSのメリット
1. 実装がシンプル
再帰を使うことで、短いコードで書けるのが大きな利点です。
2. メモリ効率が良い
探索候補をすべて保持する必要がないため、比較的少ないメモリで動作します。
3. 解を早く見つける可能性がある
運が良ければ、深い位置にある解にすぐ到達できます。
DFSのデメリット
1. 最短経路は保証されない
DFSは深さ優先のため、最短ルートを見つけるのには向いていません。
2. 無限ループのリスク
グラフ構造では、同じノードを何度も訪れる可能性があります。
→ 対策として「訪問済み管理」が必要です。
3. 深すぎる探索の問題
探索が深くなりすぎると、処理時間が長くなる可能性があります。
幅優先探索（BFS）との違い
DFSとよく比較されるのが幅優先探索（BFS）です。
BFSの特徴
- 同じ距離のノードを順番に探索
- 最短経路を見つけるのに適している
DFSとBFSの比較
| 項目 | DFS | BFS |
|---|---|---|
| 探索方法 | 深く進む | 横に広がる |
| データ構造 | スタック | キュー |
| 最短経路 | 保証しない | 保証する |
| メモリ使用量 | 少ない | 多い |
DFSの活用例
DFSはさまざまな分野で利用されています。
アルゴリズム・プログラミング
- グラフの全探索
- パズルの解探索
- 組み合わせ問題
AI分野
- ゲームの状態探索
- 探索問題の解決
実務的な例
- ファイルシステムの階層探索
- Webクローラー（ページ巡回）
日本の開発現場でのポイント
日本のエンジニアリング現場でも、DFSは以下のような場面で重要です。
- コーディング試験（アルゴリズム問題）
- データ構造の理解
- システム設計（探索ロジック）
特にITエンジニアを目指す方にとっては、必須の基礎知識といえます。
まとめ
深さ優先探索（DFS）は、基本かつ重要な探索アルゴリズムです。
- 奥まで進んでから戻る探索手法
- スタックや再帰で実装可能
- メモリ効率が良い
- ただし最短経路探索には不向き
AIやアルゴリズムの理解を深めるためには、DFSとBFSの違いをしっかり押さえておくことが重要です。
基礎をしっかり理解することで、より高度なAI技術の学習にもスムーズに進めるようになります。
こちらもご覧ください：探索木とは？AIやアルゴリズムで重要な「高速検索」の仕組みをわかりやすく解説
