深さ優先探索とは
深さ優先探索（ふかさゆうせんたんさく）とは、グラフや木構造などのデータ構造を探索するための代表的なアルゴリズムの一つです。英語の「Depth-First Search」の頭文字をとって「DFS」とも呼ばれます。この探索法の特徴は、ある経路を選んだら、突き当たり（葉ノード）に達するまでひたすら深く進み、行き止まりになったら一歩戻って（バックトラック）別のルートを探索する、という手順を繰り返すことです。メモリの消費量を抑えやすいという特徴があり、迷路の全ルートを調べたり、パズルなどの条件を満たす組み合わせをすべて列挙する問題に適しています。実装には「スタック」や「再帰」が用いられます。
具体例
一本道を進んで行き止まりにぶつかったら、最後の分岐点まで戻って別の道を進むという「迷路の探索」そのものです。木構造のフォルダの中にファイルを探しに行く場合、まず一番上のフォルダに入り、さらにその中のサブフォルダに深く潜っていき、ファイルがなければ戻って次のフォルダを調べるという手順がこれに該当します。
もう少し詳しく
深さ優先探索（DFS: Depth-First Search）は、目的のデータを見つけるため、あるいは全ての可能性を網羅するために、ツリー構造やグラフ構造を効率的に辿るアルゴリズムです。その最大の技術的特徴は、「スタック（後入れ先出しのデータ構造）」、またはプログラミング言語の「再帰呼び出し」を利用して実装される点にあります。
探索の過程では、現在いるノードからまだ訪れていない隣接ノードを一つ選び、そこへ移動します。これを限界に達するまで繰り返します。限界に達した（それ以上進めなくなった）ノードを「葉（リーフ）」と呼びますが、葉に到達すると、直前の分岐点まで戻ります。これを「バックトラック（後戻り）」と呼びます。そして、戻った分岐点から別の未訪問のルートを再び深く探索していきます。このプロセスを繰り返し、すべてのノードを訪問し終えるか、目的のデータを見つけた時点で探索が終了します。
対をなすアルゴリズムとして「幅優先探索（BFS）」がありますが、BFSが探索中のすべての分岐状態をメモリ（キュー）に保持しなければならないのに対し、DFSは現在辿っている「一つの経路（現在地までのルート）」だけをスタックに記憶しておけば済むため、使用するメモリ量が非常に少なく済むという大きな利点があります。そのため、チェスや将棋のような複雑なゲームの思考ルーチン（次の一手の先読み）や、迷路の最短ルートではなく「出口にたどり着くルートが一つでもあれば良い」といった問題、また順列や組合せをすべて生成するような場面で極めて強力な手法となります。
試験でのポイント
基本情報技術者試験などのIT国家試験において、深さ優先探索はアルゴリズムやデータ構造の問題で頻繁に出題されます。特に重要なポイントは以下の3点です。
1つ目は、「スタック（Stack）」との関連性です。「深さ優先探索を実装する際に用いられるデータ構造はどれか」という問題が出た場合、正解は必ず「スタック」になります。スタックは「最後に入れたデータを最初に取り出す（LIFO: Last In First Out）」という性質を持っており、これが直前の分岐点に戻るバックトラックの動きと完全に一致するからです。なお、キュー（Queue）は幅優先探索で用いられるため、引っかけの選択肢としてよく登場するので注意が必要です。
2つ目は、「木構造の巡回順序」に関する問題です。二分木（各ノードが最大2つの子を持つ木構造）を深さ優先探索で巡回する順序には、「先行順（行きがけ順）」「中間順（通りがけ順）」「後行順（帰りがけ順）」の3種類があります。試験では「図で示された木を中間順で巡回したときに、ノードを訪問する順番として正しいものはどれか」といった問題がよく出ます。左の子、親、右の子という順番で辿るのが中間順など、それぞれの定義をしっかりと図に描いてトレースできるようにしておくことが不可欠です。
3つ目は、「再帰アルゴリズム」との組み合わせです。疑似言語を用いたプログラミング問題において、深さ優先探索は関数が自分自身を呼び出す「再帰処理」を使って記述されることがほとんどです。プログラムのトレース問題が出た際には、関数がどの深さまで呼び出され、どのタイミングで値が返ってくるか（再帰の終了条件は何か）を、余白にスタックの状態をメモしながら落ち着いて追いかける計算力が求められます。
関連する用語
幅優先探索、スタック、再帰呼び出し