深さ優先探索

2025年10月21日

深さ優先探索

英語表記: Depth-First Search

概要

深さ優先探索（DFS）は、グラフ構造やツリー構造といった複雑なデータ構造を巡回したり、特定の要素を探し出したりするための基本的なアルゴリズムの一つです。この手法は、一つの経路を選んだら、その道の終点まで「可能な限り深く」掘り進んでいくことを特徴としています。そして、この「深く潜って、行き止まりなら戻る」という動作を実現するために、データ構造の一つである「スタック」をその代表的な用途として利用している点が非常に重要です。

詳細解説

探索の目的と動作原理

深さ優先探索の主な目的は、ツリーやグラフの全てのノード（頂点）を漏れなく訪問すること、あるいは特定の条件を満たすノードを見つけ出すことです。

動作は非常に直感的です。まず、探索を開始するノード（始点）を選びます。そこから、まだ訪問していない隣接ノードがあれば、そちらに移動し、さらに深く進んでいきます。例えるなら、一本の道を選んだら、脇道に逸れずにその道が途切れるまでひたすら歩き続けるイメージです。

もし行き止まりに到達したり、そのノードから先の全ての経路がすでに訪問済みであったりした場合は、一つ前に戻り、まだ試していない別の経路を探し始めます。この「戻る」動作が、深さ優先探索の核心であり、データ構造の「スタック」が不可欠となる理由です。

スタックの役割（タクソノミとの関連）

本稿が「データ構造（リスト, スタック, キュー, ツリー） → スタック → 代表用途」という文脈で深さ優先探索を扱っているのは、スタック（Stack）の特性がこのアルゴリズムの動作原理と完全に一致するからです。

スタックは「後入れ先出し」（LIFO: Last In, First Out）という性質を持つデータ構造です。深さ優先探索では、次に探索すべき候補ノードをスタックに格納していきます。

あるノードAを訪問しました。
ノードAには子ノードB、C、Dがあるとします。
スタックにD、C、Bの順でノードをプッシュ（格納）します。
最も深く潜るために、スタックから最後にプッシュしたBを取り出して（ポップ）、Bに移動します。
Bからさらに深く潜り、最終的に行き詰まりました。
次に探索を再開すべき場所は、直前に分岐したノードAに戻って、まだ試していない経路です。スタックを見ると、次にCが待機しています。

このように、スタックを使うことで、深く潜った後、自然に直前の分岐点に戻り、未探索の経路を優先的に選ぶことができるのです。キュー（FIFO: 先入れ先出し）を使う幅優先探索（BFS）とは対照的に、LIFOの性質が「深さ」を重視した探索を実現している、非常に美しい関係性だと思います。

計算量と効率

深さ優先探索は、グラフのノード数をV、エッジ（辺）の数をEとした場合、O(V+E)という非常に効率的な計算量で動作します。これは、基本的に全てのノードとエッジを一度ずつチェックするだけで済むことを意味します。メモリ効率の面では、探索の深さに応じたスタック領域しか必要としないため、幅優先探索よりも優れている場合が多いです。

具体例・活用シーン

深さ優先探索は、その性質上、特定の目標にたどり着くまでの経路を素早く見つけたい場合に非常に有効です。

迷路の探索（メタファー）

深さ優先探索を理解するための最も有名な例は「迷路の探索」です。

想像してみてください。あなたは巨大な洞窟の迷路を探検する探検家です。あなたは、入り口から一つの通路を選び、脇目も振らずにその奥へと進みます。

深く潜る: 通路が分岐するたびに、あなたは「この道を行き止まりまで試すぞ！」と心に決め、目印として「まだ試していない他の道」をメモ帳（これがスタックです）に書き残します。
行き止まり: 突き当りまで来てしまい、これ以上進めなくなりました。
戻る: あなたは来た道を戻り、メモ帳（スタック）の「一番上に書かれている（最後に記録した）」分岐点に戻ります。そして、まだ試していない別の道を選んで、再び深く潜り始めます。

この「行き止まりまで進む → 戻る → 別の道を試す」という繰り返しこそが、深さ優先探索そのものです。

活用シーン

経路探索: GPSナビゲーションで、ある場所から別の場所への具体的な経路を一つ見つけ出す際に使われます。
ウェブクローラー: 検索エンジンのクローラーがウェブサイトのリンクをたどって情報を収集する際、特定のサイトの深い階層まで情報を取得するために利用されることがあります。
トポロジカルソート: プロジェクト管理などで、タスク間の依存関係を考慮して実行順序を決定する際（グラフ構造の巡回）に応用されます。

資格試験向けチェックポイント

深さ優先探索は、基本情報技術者試験や応用情報技術者試験において頻出のテーマであり、特に「データ構造とアルゴリズム」の分野で重要視されます。

スタックの利用: 深さ優先探索（DFS）は、データ構造として必ず「スタック」を使用することを確実に覚えてください。これに対し、幅優先探索（BFS）は「キュー」を使用します。この対比は最も基本的な出題パターンです。
探索順序: ツリー構造におけるノードの巡回順序（前順、中順、後順）と、DFSがどのように関連しているか理解しておく必要があります。DFSは基本的に前順探索（行きがけ順）の考え方に近いです。
BFSとの比較:
- DFS: 経路を一つ見つけるのが速い。メモリ使用量が少ない（探索の深さに依存）。最適解が見つかるとは限らない（グラフが無限大の場合）。
- BFS: 最短経路を見つけるのに適している。メモリ使用量が多い（全てのノードを記憶する必要があるため）。
実装方法: 再帰呼び出し（関数が自分自身を呼び出す）を使って簡潔に実装できることも特徴の一つです。再帰呼び出しの裏側では、システムがコールスタック（スタック）を用いて処理を管理しています。