深さ優先探索と幅優先探索とは？ふかさゆうせんたんさくとはばゆうせんたんさく
深さ優先探索と幅優先探索とは、グラフや木を全探索する二大方式。深さ優先は行けるところまで進んでから戻る方式でスタック（または再帰）を使い、幅優先は始点から近い順に層状に広げる方式でキューを使う。どちらを使うかで得られる解の性質と必要メモリが変わる。
最終更新：2026-10-06
応用情報を最短で暗記・合格する →具体例
辺の重みがすべて等しいグラフで最短経路（最小手数）を求めるなら幅優先が適し、迷路の全経路列挙や連結成分の判定なら深さ優先が向く。幅優先は同じ層の節点をすべて保持するため、分岐が多いグラフではメモリを大量に消費する。
試験での引っ掛け
深さ優先で最初に見つかった経路を最短経路と思い込む誤り。使用するデータ構造（深さ優先＝スタック、幅優先＝キュー）の取り違えも定番の出題。
関連用語
出典・参考
解説は資格暗記が独自に作成しています。過去問の出典は各問題に記載のとおりです。