DFS (深さ優先探索)（DFS: ディーエフエス）
英語表記: DFS (Depth-First Search)
概要
DFS（深さ優先探索）は、グラフや木構造といったデータ構造を系統的に探索するための基本的なアルゴリズムの一つです。この手法は、「アルゴリズムと計算量」カテゴリの中でも特に「グラフアルゴリズム」に分類される、非常に重要な「基本探索」技術です。探索を開始したノードから見て、可能な限り深く（遠いノードへ）進むことを優先するのが最大の特徴です。行き止まりに到達するまで探索を続け、行き詰まったら一つ前の分岐点に戻って（バックトラック）、まだ探索していない別の道を探します。
詳細解説
グラフ探索におけるDFSの位置づけ
DFSは、グラフ構造を探査する二大巨頭の一つ（もう一つはBFS：幅優先探索）であり、特定のノードを見つけたり、グラフ全体を漏れなく巡回したりする目的で利用されます。私たちがグラフアルゴリズムを学ぶ上で、このDFSの動作原理を理解することは、複雑な問題解決の第一歩となります。この手法は、探索の効率性を保証するため、「アルゴリズムと計算量」の分野で基本として位置づけられています。
動作原理：深さを優先する戦略
DFSの核となる戦略は、「とにかく前へ、前へ」と進むことです。これは、目の前の道を極めるまで進み続ける、非常にストイックな探索方法だと言えますね。
- 開始ノードの選択と訪問: 探索を開始するノードを選び、そのノードを「訪問済み」として記録します。これは、同じ場所を何度も訪れて無限ループに陥るのを防ぐために非常に重要です。
- 深く潜る: 現在訪問しているノードから、まだ訪問していない隣接ノードを一つ選び、そこへ移動します。
- 再帰的な進行: 移動先のノードでも、同じルールを適用し、さらに深く進みます。この時、進むべきノードの履歴はスタック（後入れ先出し：LIFO）というデータ構造で管理されます。スタックを使うことで、直前に来た場所を優先的に覚えておくことができ、深さ方向への探索が自然と実現されます。
- バックトラック: 行き止まり（隣接するノードが全て訪問済み、または存在しない）に到達したら、スタックから一つ前のノードを取り出し、そこに戻ります。これを「バックトラック（後戻り）」と呼びます。バックトラックによって、まだ探索していない別の分岐点を探しに戻ることができるのです。
なぜ「基本探索」なのか
DFSは、グラフの接続性判定、閉路（サイクル）の検出、トポロジカルソートなど、より高度なグラフアルゴリズムの基礎として機能します。計算量は一般的に$O(V+E)$で表現されます（$V$は頂点数、$E$は辺数）。これは、グラフの全ての頂点と辺をせいぜい一度ずつチェックするだけで済むことを意味しており、非常に効率的です。
DFSは、幅優先探索（BFS）とは異なり、最短経路を見つけるのには向きませんが、グラフの構造（特に経路の存在や接続性）を素早く把握するのに優れています。この汎用性と効率性から、DFSは「グラフアルゴリズム」における「基本探索」の柱として、学習が必須とされているわけです。
再帰による実装の美しさ
DFSは、再帰呼び出し（関数が自分自身を呼び出す）を使って実装されることが多いです。この再帰的なアプローチは、コードを非常に簡潔かつエレガントにするため、プログラミング学習者にとっては理解の醍醐味の一つとなります。再帰は本質的にスタック構造を利用しており、深さ優先の動きを自然に表現できるのが素晴らしい点です。
具体例・活用シーン
迷路探索の探検家 (比喩・ストーリー)
DFSの動作を最もよく表す具体例は、「迷路の探索」です。迷路の入り口に立っている勇敢な探検家（あなた）の行動を想像してみてください。
- 糸を辿る: あなたは進む道筋を記録するために、長い糸（スタックの役割）を持っています。
- 深く、深く: あなたは一つの道を選んだら、脇道に逸れることなく、壁にぶつかるまで、とにかくまっすぐ進み続けます。これが「深さ優先」です。もしその道がゴールに繋がっていればラッキーですが、多くの場合、行き止まりにぶつかります。
- 後戻りの知恵: 行き止まりにぶつかったら、あなたは手元の糸を辿って、直前の分岐点（まだ探索していない道があった場所）まで戻ります（バックトラック）。
- 未踏の道へ: 分岐点に戻ったら、まだ入ったことのない別の道を選び、再び壁にぶつかるまで深く進みます。
この探検家は、まず一つの可能性を徹底的に調べ尽くすことで、迷路全体を効率的に探索しようとしています。迷路の解法や、コンピュータゲームにおけるAIの経路探索など、行き止まりを恐れずにまず深く潜って全体像を把握したい場合に、DFSは非常に強力なツールとなります。
実際の活用シーン
- トポロジカルソート: プロジェクトのタスク管理やコンパイル時の依存関係解決など、順序付けが必要な場面でDFSが活躍します。「Aの作業が終わらないとBの作業は開始できない」といった依存関係をグラフで表現し、DFSを使って矛盾なく並べ替えることができます。これは、複雑なシステムを構築する上で欠かせない技術です。
- バックトラッキングを伴う問題: 数独の解法や、チェスのクイーン配置問題など、試行錯誤を繰り返しながら解を見つけるタイプの問題（バックトラッキングアルゴリズム）の基盤としても利用されます。DFSは、ある選択肢を選んだ後に、それが失敗だった場合に直前の状態に戻る（バックトラック）仕組みを提供します。
*
