【G検定】深さ優先探索とは？メモリ節約型の縦型探索と幅優先との違いを解説

迷路で「とにかく一本道を突き進み、行き止まりなら引き返して別の道へ」という探し方をしたことはありませんか。それがまさに深さ優先探索です。メモリが少なくて済む代わりに、最短の解が見つかるとは限らない——幅優先探索と対になるこの性質が試験の核心です。

📖 ひと言でいうと

深さ優先探索とは、探索木の1つのノードから可能な限り深く進み、行き止まりに達したら1つ前のノードに戻って別の枝を調べ直す探索手法です。たとえるなら、洞窟探検で1本の通路を突き当たりまで進み、ダメなら分岐点まで戻って隣の通路に入るやり方です。木を縦方向に深く掘り進む動きから縦型探索とも呼ばれます。

🖼 1枚でわかる深さ優先探索

📘 対策テキストの説明

深さ優先探索は、一つのノードから可能な限り深く探索を進め、行き止まりに達したら一つ前のノードに戻って再度探索を行う手法である。この方法は、メモリの使用量が少なくて済むが、必ずしも最短距離でゴールに到達するわけではない。運に左右される要素も含まれている。また、「縦型探索」とも称される。

要素は4つです。①動き方は「可能な限り深く進み、行き止まりで1つ前に戻る」。②長所はメモリの使用量が少ないこと。③短所は最短距離の解が保証されないことで、どの枝を先に選ぶかという「運」に結果が左右されます。④別名は縦型探索。幅優先探索の説明とちょうど鏡写しになっていることに注目してください。

🔍 しっかり理解する

探索の動き——進む・戻る・また進む

深さ優先探索の基本動作は「進めるだけ進む」「ダメなら戻る」の繰り返しです。

この「1つ前に戻ってやり直す」動きはバックトラックと呼ばれます。ゴールが見つかるまで、木のすべての枝をこの要領で順にたどっていきます。

実現のイメージとしては、幅優先探索が「先に見つけたノードから順に処理する待ち行列」で動くのに対し、深さ優先探索は「後から見つけたノードを先に処理する積み上げ（スタック）」で動きます。新しく見つけた枝先を積み上げの一番上に置き、常に一番上から取って進む——だから探索はどんどん深い方へ向かい、行き詰まったら積み上げの下（=手前の分岐）に自然に戻るのです。

なぜメモリが少なくて済むのか

深さ優先探索が覚えておくべきものは、基本的に「いま自分がたどってきた1本の経路（根から現在地まで）と、各分岐でまだ試していない枝」だけです。幅優先探索のように「同じ深さのノード全部」を抱え込む必要がありません。

探索木は深くなるほど各階層のノード数が爆発的に増えるため、「階層を丸ごと記憶する幅優先」と「1本の経路だけ記憶する深さ優先」のメモリ差は、木が大きいほど際立ちます。メモリが限られた環境や、非常に深い木を扱う場面で深さ優先探索が好まれる理由です。

たとえば各ノードから3本ずつ枝が分かれる木の深さ15の階層には、約1,400万ものノードがあります。幅優先探索はこの階層をまとめて記憶しながら進むことになりますが、深さ優先探索が覚えるのは根から現在地までのたった15ノード分の経路です。この差が「メモリの使用量が少なくて済む」という定義文の実体です。

なぜ最短の解が保証されないのか——「運」の意味

深さ優先探索は、最初に選んだ枝の先を徹底的に調べてから隣の枝に移ります。もしゴールへの近道が「2番目に試す枝」の浅い位置にあっても、先に「1番目の枝」の奥深くで別の遠回りな解を見つけてしまえば、それが最初の答えになります。つまり最初に見つかる解の質は、枝を調べる順番次第なのです。対策テキストの「運に左右される要素も含まれている」とは、この枝順への依存性を指しています。運が良ければ幅優先より圧倒的に早く解に当たることもあり、悪ければ大回りになる——ギャンブル性のある探索だといえます。

💡 具体例で考える

ファイル探しの場面が、深さ優先探索の実感しやすい例です。パソコンで「あの書類はどこだっけ」とフォルダを探すとき、多くの人は「ドキュメント→仕事→2026年→7月」と1つの系統を深く開けていき、なければ1つ上の階層に戻って隣のフォルダを開けます。これはまさに深さ優先探索とバックトラックの動きです。

このやり方なら、頭の中に「いま開いている階層のたどり道」さえ覚えておけばよく、全フォルダの一覧を記憶する必要はありません（メモリが少なくて済む）。一方、目当てのファイルが実は浅い階層の別フォルダにあった場合、深い枝を先に選んでいると発見はずっと後になります（最短性の保証がない・運に左右される）。深さ優先探索の長所と短所が、日常の行動の中にそのまま現れている例です。

⚠️ よくある誤解・紛らわしい用語

📝 試験でのポイント

📚 まとめ