深さ優先探索とは？
深さ優先探索とは、グラフや木をたどるとき、行けるところまで先へ進み、行き止まりになったら1つ戻って別の枝を試す探索方法。スタック（または再帰呼出し）で実装される。全ての経路を列挙する問題や、迷路の解探索などに向く。
ふかさゆうせんたんさく
深さ優先探索の意味
グラフや木をたどるとき、行けるところまで先へ進み、行き止まりになったら1つ戻って別の枝を試す探索方法。スタック（または再帰呼出し）で実装される。全ての経路を列挙する問題や、迷路の解探索などに向く。
深さ優先探索の具体例
根A、子にB・C、Bの子にD・Eがある木なら、たどる順はA→B→D→（戻る）→E→（戻る）→Cとなる。訪問済みの印を付けないと、閉路のあるグラフでは同じ頂点を無限にたどってしまう。
深さ優先探索は試験でどう引っ掛けられる？
幅優先探索との取り違えが最頻出。深さ優先はスタック、幅優先はキューを使う点で区別する。また深さ優先で最初に見つかった経路が最短とは限らない（最短を保証するのは重みなしグラフでの幅優先）。
最終更新：2026-08-25／解説は資格暗記が独自に作成しています。 過去問の出典は各問題に記載のとおりです。