【ふかさゆうせんたんさく】
深さ優先探索（DFS） とは？
最終更新:
💡 深く進んで戻り、まだ調べていない枝へ進む
未訪問の頂点へ深く進み、先がなくなれば戻って別の枝を調べる探索方法。訪問済み管理、探索順序、DFSとBFSの違い、再帰の深さやメモリの注意点を解説します。
📌 このページのポイント
ひよこ 深さ優先探索は、どう進むの？
ペンギン先生 今いる頂点から、まだ訪問していない隣の頂点へ進み、その先も同じように探すよ。先がなくなったら戻り、まだ調べていない枝へ進む。たとえばAの左の枝B、その先Dを調べてから、Bへ戻ってEへ進むんだ。
ひよこ 戻るときも、DからEへ直接行く？
ペンギン先生 DとEの間に辺がなければ、そういう移動ではないよ。初めて訪問する順がD→Eでも、探索の処理はDからBへ戻って、BからEへ進む。訪問順の一覧と、グラフ上の辺を区別しよう。
ひよこ ループのあるグラフだと、終わらなくならない？
ペンギン先生 ひよこ BFSより、いつも少ないメモリで済む？
ペンギン先生 木の形によって、深い探索と広い探索で必要な領域は変わるよ。一般のグラフではDFSにも訪問済み管理が必要なので、現在の経路だけ覚えればよいとは言えない。隣接リストで全体を探索する標準的なDFSの時間計算量はO(V＋E)だ。
ひよこ 再帰が深くなりすぎたら、どうする？
もっと詳しく知りたい人へ
DFSで見つけた道は、最短経路？
一般のグラフでは保証しません。辺の重みがない、またはすべて同じ重みの場合、BFSは辺の本数が最少の経路を求める用途に使えます。重みが異なる場合は別の条件とアルゴリズムを検討します。木には2頂点間の単純な経路が1つという性質がありますが、一般のグラフと混同しないようにします。
左から右へ調べる順は決まっている？
DFSの定義では固定されていません。隣接頂点の列挙順やスタックに積む順によって、訪問順が変わります。図では左の子を先に調べる例を使っています。探索順の再現が必要な場合は、列挙順もそろえます。
まとめ：ざっくりこれだけ覚えればOK！
「DFS」って出てきたら「深く進んでから戻る探索方法」と思えばだいたいOK！
📖 おまけ：英語の意味
「Depth-First Search」 ＝ 深さを優先する探索
💬 隣の枝を先に広げるより、選んだ枝の先へ進むことを優先する名前です。左側から探すこと自体が定義ではありません。