深さ優先探索（DFS）の概要
DFSの基本概念
深さ優先探索（DFS）は、探索対象の頂点を起点から順にたどり、分岐があっても可能な限り深い位置まで進んでから、行き止まりに到達した時点で戻り別の分岐を調べる手法である。探索の進行は「進めるだけ進む」方針で特徴づけられ、結果として探索木（または探索経路の構造）を自然に形成する。
DFSは、経路の発見というよりも、探索対象の構造を把握することに強みがある。たとえば、どの頂点へ到達できるか、到達の範囲がどの程度か、訪問の重複がどのように抑制されるかといった観点で重要な役割を担う。
DFSで扱う対象
木
木（tree）は、閉路を持たない連結なグラフとして扱えるため、DFSでは親子関係に沿って自然に分岐をたどることになる。根を定めれば、DFSの進行は「根から下方向へ辿る」形になり、行き止まりは葉に対応する。訪問管理が適切であれば、同じ頂点を繰り返し調べる必要は基本的に生じない。
さらに、木では探索の結果として得られる深さ情報や、探索順に基づく列の生成が容易である。これらは後続の処理、例えば部分構造の評価や、再帰的な性質を持つアルゴリズムの土台として利用される。
グラフ（有向・無向）
グラフ（graph）では、頂点間に経路が存在し得るだけでなく、閉路もあり得るため、訪問済み管理が不可欠になる。無向グラフでは辺が双方向に作用し、有向グラフでは辺の向きに従って到達が制限される。DFSの訪問順や探索木の形は、辺の並び順（隣接リストの順序など）に影響されるが、訪問済み判定の設計が正しさを左右する点は共通する。
また、有向グラフに対してDFSを行うと、到達可能性の調査だけでなく、到達の順序に関連する特徴量を導ける場合がある。これにより、構造解析や関連アルゴリズムの入力生成にもつながる。
訪問順序の考え方
DFSの訪問順序は、ある頂点から次に調べる隣接頂点の選択規則で決まる。隣接リストが与えられているとき、リストに現れる順番に従って探索すれば、同じグラフでも異なる訪問系列が生じうる。
この順序性は偶然ではなく、探索が「スタック的」に振る舞うために現れる。再帰呼び出しや明示的スタックにより、選んだ隣接頂点の探索が完了するまで他の候補が待機する。その結果、最初に選ばれた分岐が深く掘り下げられる性質が訪問系列に反映される。
アルゴリズム
再帰による実装
擬似コードの構成
再帰実装では、関数 DFS(v) が頂点 v から開始して隣接先を順に処理する。典型的には次の要素が含まれる。まず訪問状態を記録し、次に隣接頂点を走査する。そして未訪問の隣接頂点に対して再帰呼び出しを行う。
擬似コードの骨格としては、「訪問済み集合への追加」と「隣接先の走査」「未訪問であれば再帰呼び出し」の三点が中心となる。再帰の深さは探索の進行をそのまま反映するため、実装の直観として理解しやすい。
末端到達とバックトラック
DFSが行き止まりに到達すると、再帰呼び出しは戻り始める。ここで戻ることは、探索木においてある頂点の子方向の探索が完了したことを意味する。戻りの後は、同じ頂点における未処理の隣接候補が存在すれば、それを次の探索対象として選ぶ。
この戻りは「バックトラック」と呼ばれる。再帰の性質により、バックトラックはコールスタックのアンワインドとして自然に現れるため、明示的に経路を戻す処理を記述しなくても探索が成立する。
反復（スタック）による実装
明示的スタックの管理
反復実装では、再帰の代わりに自前でスタックを用意する。探索対象の頂点をスタックへ積み、取り出して隣接先を追加していくことで進行を再現する。
スタックへの積み方には複数の流儀があり、探索順の一致を厳密に求める場合は、隣接先の追加順を調整する必要がある。とはいえ、核心は「現在の探索状態をスタックで保持し、深い探索が優先される構造」を作る点にある。
訪問済み判定の手順
反復実装でも訪問済み判定は重要である。訪問済み判定のタイミングには二つの典型がある。第一は、頂点をスタックへ積む段階で訪問済みを確定する方法である。第二は、スタックから取り出した時点で初めて訪問済みを確定する方法である。
前者は同一頂点が複数回スタックに積まれるのを防ぎやすい。後者は実装が簡潔になり得る一方で、重複積みを許容する設計になるため、追加のチェックや管理が必要になることがある。どちらを選ぶかは、計算量の見積りと実装の都合で決められる。
初期化と探索開始点
単一始点
単一始点のDFSは、特定の頂点 s から探索を開始し、到達可能な範囲を訪問することを目的とする。訪問済み集合を空から始め、s を起点として探索を進めればよい。
この形は到達可能性の判定や連結性の一部の評価に直結する。特定の出発点から先に存在する構造を調べたい場合に適している。
全頂点探索（連結でない場合）
グラフが連結でない場合、単一始点からでは全頂点を網羅できない。そのため、通常は全頂点を走査し、未訪問の頂点を新たな開始点としてDFSを繰り返す。
この反復により、分断された領域ごとに探索が行われ、訪問済み集合を通して「どの領域がどこから到達可能か」が整理される。連結成分の列挙や、到達可能性を領域単位で整理する手続きへと自然に接続する。
正しさと計算量
正しさの直観（訪問済みの役割）
DFSの正しさは、訪問済み集合が「重複訪問を抑えつつ、到達可能なものを取りこぼさない」ことに支えられている。訪問済みがあることで閉路が存在しても無限に探索が続かない。一方で、未訪問として残っている頂点は、ある時点で隣接関係により到達できるはずなので、訪問されるべき対象として扱われる。
探索順そのものは辺の並びに依存して変わり得るが、到達範囲の完全性という観点では、訪問済み判定が適切なら保証が得られる。つまり、DFSの本質的な正しさは「到達可能性と停止性の両立」にある。
計算量
隣接リストの場合
隣接リスト表現では、各頂点について隣接リストを一度ずつ走査する設計が典型である。訪問済みの管理により同一頂点の探索本体は高々一度行われるため、全体の時間は概ね O(V + E) に収まる。ここで V は頂点数、E は辺数を表す。
隣接リスト上での走査は、辺に対応する要素の総数として整理できるため、辺数に比例する項が現れる。さらに頂点の訪問処理や訪問済み判定などの付随作業も頂点数に比例する。
隣接行列の場合
隣接行列では、ある頂点の隣接先を探す際に全列（または全行）を走査する必要がある。したがって、各頂点で O(V) の走査が必要になり、全体では O(V^2) が基本となる。
この表現では辺の疎密に関わらず探索の隣接検査コストが固定的に大きくなる傾向がある。結果として、疎なグラフでは隣接リストより不利になりやすい。
記憶量
再帰スタック
再帰実装では、関数呼び出しが深さ方向に積み重なる。最悪の場合、スタックの深さは探索の深さに対応し、木や到達可能領域が細長い形だと O(V) まで増える可能性がある。これが主な追加の記憶要素になる。
また、訪問済み集合も O(V) の領域を要求する。したがって、全体の補助記憶は通常 O(V) と見積もられる。
明示的スタック
反復実装でも、スタックは探索の進行に応じて増減する。最悪ケースでは頂点数に比例する量が保持され得るため、スタックの最大サイズは O(V) となる。
訪問済み集合に加え、明示的スタックを保持する分が補助記憶となるため、再帰実装と同程度の O(V) 規模になりやすい。実行環境によっては、再帰の代わりに反復を選ぶことでスタックオーバーフローの回避が容易になる。
応用分野
到達可能性と連結性
連結成分の列挙
連結成分の列挙は、未訪問の頂点を起点にDFSを繰り返すことで実現できる。各DFS呼び出しで訪問される頂点集合が一つの成分に対応し、成分数や成分ごとのサイズを計算できる。
無向グラフでは連結、さらに有向グラフでは到達可能性の方向が影響するため、成分の概念が異なる。とはいえ、DFSという枠組みが「到達可能領域を成分として取り出す」ための基本構造である点は共通する。
グラフ探索による到達判定
到達判定は、ある始点から指定した終点へ至れるかを調べる用途に向く。DFSは深い探索を優先するため、探索順の性質が一致しない場合でも、訪問済み集合に基づけば到達可否は正しく決定できる。
さらに、終点が見つかった時点で探索を打ち切る設計も可能である。これにより実際の計算量を下げられる場合があるが、最悪計算量の見積りは変わらないことがある。
探索木と深さ情報
DFS木
DFSを実行すると、訪問の親子関係によって探索木（DFS木）が定義できる。これは「未訪問の頂点を初めて訪れたときに、その頂点へ至った辺」を基準にして構成される。
探索木は、単なる到達の記録にとどまらず、後続処理で利用できる構造として現れる。たとえば各頂点の親、探索の順序に付随する関係、深さの変化などが、アルゴリズムの派生における入力情報として扱える。
深さ（レベル）の導出
深さ（レベル）は、探索木における根からの距離として定義されることが多い。再帰実装では、再帰の深さそのものが深さ情報に対応し、反復実装でもスタックに深さを併せて保持すれば同様に導出できる。
深さ情報は、木の特徴量の計算や、特定の層にある頂点の抽出などに利用される。さらに、探索木の形を通じて構造の偏りを把握する観点でも意味を持つ。
典型的な関連アルゴリズムとの関係
幅優先探索（BFS）との比較
BFSは幅方向に広げていく探索であり、同じグラフでも到達の順序や得られる性質が異なる。特に、BFSは無重みグラフにおいて最短経路（辺数最小）の探索と相性が良い。一方DFSは深掘りを優先するため、最短性の保証は一般には得られない。
ただし、DFSは探索木の性質からサイクルの存在確認や、帰納的な構造解析に向く場面がある。両者の使い分けは目的関数と期待する性質（最短性、到達範囲、構造の特徴抽出など）に依存する。
トポロジカルソートへの応用（関連手法として）
トポロジカルソートは、有向非巡回グラフにおける順序付け問題として知られる。DFSはこの問題と関連して用いられることがあり、探索の完了時刻（処理が終わった順）を利用して順序を組み立てる方法がある。
具体的には、頂点の「終了」に基づいてリストへ要素を追加し、最後に逆順を取るといった構成が典型である。この流儀では、閉路がないことが前提となり、DFSが生成する探索木と完了順の整合性が順序付けを支える。