深さ優先探索 (G検定)

2026年8月12日2026年9月2日

G検定

1. 定義と概要

深さ優先探索（Depth-First Search、DFS）とは、探索木（問題の選択肢や判断の過程を、枝分かれする木の形で表した図）やグラフ（点と点をつなぐ線で表現したデータの構造）における探索方法です。その探索方法では、あるノード（探索木を構成する一つ一つの点）から一つの枝をたどっていきます。

行き止まり（それ以上先に進めない状態）まで進んだら、そこから一つ手前のノードに戻って別の枝を試すという手順を繰り返します。この「行き止まりで一つ前に戻る」動作をバックトラック（行き止まりに来たら一つ前まで戻ってやり直すこと）と呼びます。

迷路の一本道をとことん進み、行き止まりに来たら引き返して別の道を試す動き方が、この探索の典型的なイメージです。深さ優先探索は、英語表記の頭文字をとってDFSと略され、日本語では縦型探索とも呼ばれます。

探索木は、AIが取りうる選択肢や判断の分岐を枝分かれの形で表現する仕組みとしてよく使われます。この探索木やグラフをどの順番でたどるかを決める代表的な方法が、深さ優先探索と幅優先探索です。

幅優先探索は、出発点に近いノードから順番に、階層ごとに調べていく探索方法を指します。両者は「どのノードを優先してたどるか」という探索の方向性において、対照的な特徴を持っています。探索木そのものの構成要素や用語の詳しい整理は、関連記事のテーマに譲ります。

2. 試験対策ポイント

深さ優先探索の論点は、メリットとデメリットの両面から整理できます。幅優先探索に比べて一度に保持しておく必要のあるノード数が少なく済むため、メモリ使用量が少ないという利点があります。一方で、最初に見つかった経路が最短経路であるとは限らないという制約があり、この点は幅優先探索とは逆の性質になります。

メモリ効率と最短経路の保証はどちらも同時には成り立たず、片方を優先すればもう片方を手放す関係にあります。この二律背反の関係は、深さ優先探索と幅優先探索を理解するうえでの中心的な論点です。

実装方法には、スタック（最後に入れたものを最初に取り出すデータの積み方）を使う方法と、関数が自分自身を呼び出す再帰（同じ処理を繰り返し呼び出す方法）を使う方法の2通りがあります。再帰呼び出しの内部でも呼び出し履歴がスタックのように積まれるため、両者は同じ考え方に基づく実装だといえます。どちらの実装であっても、たどっているのは常に一本の枝の情報であり、これがメモリ使用量の少なさに直結しています。

探索する木やグラフの深さに限りがない場合には、弱点も生じます。一つの枝をどこまでも深く進み続けてしまい、行き止まりに到達できずに戻れなくなる恐れがあり、有限のグラフではこの弱点は表面化しにくい関係にあります。

探索木の図をもとに、どのノードをどの順番でたどるかを正しく追えるかどうかも、深さ優先探索の性質を理解するうえでの中心的な論点です。一つの枝を先に掘り下げるという挙動を具体的な図でイメージできるようにしておくと、理解が定着しやすくなります。

3. 関連概念との比較・相違点

深さ優先探索と幅優先探索の最大の違いは、探索木やグラフをたどる優先順位の方向性にあります。深さ優先探索は一つの枝を深く掘り下げてから次の枝に移るのに対し、幅優先探索は出発点に近いノードから階層ごとに調べます。この方向性の違いが、使うデータ構造やメモリ使用量にも波及します。

観点	深さ優先探索	幅優先探索
たどる順序	一つの枝を深く掘り下げてから次の枝へ移る	出発点に近いノードから階層ごとに調べる
使うデータ構造	スタック	キュー（先に入れたものを先に取り出すデータの並べ方）
メモリ使用量	たどっている一本の枝の情報で済むため少ない	同じ階層の多数のノードを同時に保持するため多い
最短経路の保証	保証されない	保証される
行き止まりでの動き	一つ前に戻って別の枝を試すバックトラックを取る	行き止まりという概念を持たず、階層を順に処理し尽くす

とくに取り違えやすいのが、最短経路の保証をめぐる部分です。最短経路が保証されるのは幅優先探索の側で、深さ優先探索は一つの枝を先に掘り下げる性質上、最初に見つかった経路が最短であるとは限りません。

どちらを選ぶかは、メモリの制約が厳しいか、最短経路の保証が必要かという目的によって変わる関係にあります。同じ探索木を扱う場面でも、優先したい条件によって適した方法が入れ替わります。

4. ビジネス・実務での活用シナリオ

ソフトウェア開発の現場では、ディレクトリ探索に深さ優先探索の考え方が使われます。ファイルシステムのディレクトリ構造はグラフとみなせるため、一つの階層を掘り下げてから次に移る深さ優先探索に基づく実装が採用され、限られたメモリでも網羅的な探索が可能になります。

Webサイトのリンク構造も同様にグラフとみなせるため、リンクをたどる処理に深さ優先探索の考え方に基づく実装が使われる例もあります。多数の階層を持つ構造を扱う場面ほど、メモリ効率の良さが実務上の利点として現れます。

迷路の経路探索やパズルゲームの解法探索でも、深さ優先探索の考え方は使われます。一つの手順を行き止まりまで掘り下げて確認し、条件を満たさなければ一つ前に戻ってやり直すバックトラック法として応用される場面です。総当たりに近い形で候補を確認しながらも、行き止まりに達した時点で早めに枝を切り捨てられる点が、力任せに全パターンを試す方法との違いになります。

作業の依存関係を整理する処理にも、深さ優先探索の考え方は応用されます。作業の依存関係を矛盾のない順序に並べるトポロジカルソート（依存関係のある作業を、順番が矛盾しないように並べ替えること）や、循環した参照関係の検出といった処理は、深さ優先探索の考え方を土台にして実現されています。順序に矛盾がないかを確かめるこうした処理では、枝をたどりきってから戻るという深さ優先探索の性質が土台になっています。