深さ優先探索（DFS）とは？
深さ優先探索（Depth-First Search、略してDFS）は、グラフや木構造といったデータを探索するための基本的なアルゴリズムの一つです。 その名前の通り、「深さを優先して」データを探索していく特徴があります。
迷路を解く場面を想像してみてください。 分かれ道に来たら、まず一つの道を選んで、行き止まりになるまでひたすら進みます。行き止まりにぶつかったら、一つ手前の分かれ道まで戻って、まだ試していない別の道を進みます。 このように、「行けるところまで進んで、戻って別の道を探す」というアプローチを繰り返すのが、深さ優先探索の基本的な考え方です。
基本的な仕組み
深さ優先探索は、コンピュータで実現するために「スタック」というデータ構造を利用します。 スタックは「後入れ先出し（LIFO: Last-In, First-Out）」という特徴を持ち、最後に追加したデータが最初に取り出されます。 本を積み上げて、一番上の本から取る様子をイメージすると分かりやすいでしょう。
また、深さ優先探索は再帰関数（自分自身を呼び出す関数）を使うと、非常にシンプルに実装することができます。
探索の具体的な手順は以下の通りです。
- スタート地点（ノード）から探索を開始します。
- 現在のノードに隣接していて、まだ訪れていないノードへ進みます。
- 進んだ先で、さらに行けるノードがあればそちらへ進む、という処理を繰り返します。
- これ以上進めるノードがなくなったら（行き止まり）、一つ前のノードに戻ります。
- 前に戻った地点で、まだ探索していない別の隣接ノードがあれば、そちらの探索を開始します。
- すべてのノードを訪れるまで、このプロセスを繰り返します。
幅優先探索（BFS）との違い
深さ優先探索（DFS）としばしば比較されるのが、「幅優先探索（BFS: Breadth-First Search）」です。 DFSが「深く」探索するのに対し、BFSは「広く」探索します。 BFSは、スタート地点から近い順に、まるで水面に広がる波紋のように探索を進めていきます。
この二つのアルゴリズムの主な違いを以下の表にまとめます。
| 項目 | 深さ優先探索 (DFS) | 幅優先探索 (BFS) |
|---|---|---|
| 探索の順序 | 行けるところまで深く進み、行き止まりになったら戻る。 | 現在地に近い場所から順番に、全方位を探索する。 |
| 使用するデータ構造 | スタック (後入れ先出し) | キュー (先入れ先出し) |
| 最短経路の探索 | 向いていない。最初に見つかった経路が最短とは限らない。 | 向いている。最初に見つかった経路が必ず最短経路になる。 |
| メモリ使用量 | 比較的少ない傾向がある。 | 探索対象が増えると多くなる傾向がある。 |
| 実装方法 | 再帰関数を使うとシンプルに実装できる。 | キューを使って実装するのが一般的。 |
Pythonによる実装例
ここでは、再帰関数を使った深さ優先探索の簡単なPythonコード例を紹介します。 グラフは、どのノードがどのノードに繋がっているかを示す「隣接リスト」という形式で表現します。
# グラフを隣接リスト（辞書）で表現
graph = { 'A': ['B', 'C'], 'B': ['D', 'E'], 'C': ['F'], 'D': [], 'E': ['F'], 'F': []
}
# 訪問済みのノードを記録する集合
visited = set()
def dfs(visited, graph, node): """再帰による深さ優先探索の実装""" if node not in visited: print(node, end=" ") # 現在のノードを訪問したことを示す（ここでは出力） visited.add(node) # 隣接するノードを再帰的に探索 for neighbour in graph[node]: dfs(visited, graph, neighbour)
# 'A'を始点として探索を開始
print("深さ優先探索の訪問順:")
dfs(visited, graph, 'A')
# 出力: 深さ優先探索の訪問順: A B D E F Cこのコードでは、`dfs`関数が自分自身を呼び出すことで、次のノードへと深く探索を進めています。 一度訪れたノードは`visited`セットに追加され、再度訪れることがないように管理しています。
応用例・どのような場面で使われるか
深さ優先探索は、その特性から様々な場面で応用されています。
- 迷路の解決: スタートからゴールまでの経路を一つ見つけるのに使われます。
- 連結成分の検出: グラフがいくつかの島に分かれている場合、それぞれの島（連結成分）を特定することができます。
- トポロジカルソート: 作業の依存関係（例: Aが終わらないとBが始められない）を解決し、実行可能な順序を決定する際に利用されます。
- ウェブクローラー: ウェブサイトのリンクをたどり、ページを収集する際に、特定のサイトを深く掘り下げていくような動作に応用されることがあります。
- プログラムの経路解析: プログラムがどのようなルートをたどる可能性があるかをすべて洗い出すといった、テストカバレッジの分析などに使われることがあります。
まとめ
深さ優先探索（DFS）は、「深く、深く」進むことを優先するシンプルな探索アルゴリズムです。その動きは迷路を解く様子に例えられ、スタックや再帰を用いることで実装できます。最短経路の探索には不向きですが、メモリ効率が良く、経路を一つ見つけるといったタスクで力を発揮します。対となる幅優先探索（BFS）との違いを理解することで、問題に応じて適切なアルゴリズムを選択できるようになります。