深さ優先探索とは？ふかさゆうせんたんさく
深さ優先探索とは、木やグラフをたどるとき、進める限り深く進み、行き止まりに着いたら直前の分かれ道まで戻って別の枝へ移る探索手順。戻る動作はスタック、または再帰呼出し（手続きが自分自身を呼び出すこと）で実現する。全経路の列挙や迷路の解の発見のように、どこかへ到達できるかを調べる問題に向く。
最終更新：2026-10-09
基本情報を最短で暗記・合格する →背景
道が何本にも枝分かれするグラフで、すべての頂点を抜けも重複もなく調べる手順が要る。深さ優先は「来た道を覚えておき、詰まったら1つ戻る」だけで済むので、覚えておく情報が今いる深さのぶんで足り、同じ階層の頂点をすべて抱える幅優先より記憶量が小さい。基本情報では木の走査順や再帰処理の追跡として繰り返し問われる。
具体例
根がA、その子がBとC、Bの子がDとEという木では、A→B→D→E→Cの順に訪れる。Dで行き止まりになったらBへ戻ってEへ進む動きになる。閉路のあるグラフでは訪問済みの印を付けないと同じ頂点を巡り続けるため、印の管理まで含めて手順として覚える。
試験での引っ掛け
幅優先探索との取り違えが最頻出。使うデータ構造は深さ優先がスタック、幅優先がキューで逆になる。最初に見つけた経路が最短とは限らず、重みのないグラフで最短を保証するのは幅優先のほう。先行順・中間順・後行順は深さ優先の中での訪問タイミングの違い。
関連用語
出典・参考
公式シラバスの1 基礎理論 ＞ 1. データ構造 ＞ (2) データ構造の種類に掲載されている用語です。
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。