幅優先探索と深さ優先探索（breadth-first search / depth-first search）

分類: テクノロジ系アルゴリズムとプログラミング
出る試験: 基本情報応用情報
重要度: ★★★☆☆

つながりをたどって探す2つの進め方。近いところから横に広げるのが幅優先、行けるところまで縦に進むのが深さ優先。

もう少し詳しい説明

グラフの言葉

用語	中身
グラフ	点と線で、つながり方を表したもの
ノード（節点）	点。状態や場所にあたる
エッジ（辺）	線。つながりや移動にあたる
ルートノード（根）	始めの点
子ノード	ある点から1つ進んだ先
リーフノード（葉）	その先が無い点
深さ	始めの点から何本の線をたどったか

木構造は、枝分かれだけで輪が無いグラフです。 探索の考え方は同じように使えます。

2つの進み方

	幅優先探索	深さ優先探索
進み方	近いところから横に広げる	行けるところまで縦に進む
使う入れ物	キュー（先入先出）	スタック（後入先出）または再帰
最短を保証するか	する	しない
使うメモリ	多い（同じ深さを全部持つ）	少ない（いまの道筋だけ）
英語	breadth-first search（BFS）	depth-first search（DFS）

幅優先探索が最短になる理由

手数の少ない順に調べるためです。

調べる順	中身
1回目	1手で行ける場所を全部
2回目	2手で行ける場所を全部
3回目	3手で行ける場所を全部

初めてゴールに届いたとき、それより少ない手数の道はすでに調べ終わっています。 そのため、最初に見つかったものが最短になります。

深さ優先探索は先に深く進むので、遠回りの道を先に見つけることがあります。

同じところを二度調べない

輪があるグラフでは、同じ場所に戻ることがあります。

手立て	中身
調べ終わった場所を記録する	一覧に残し、次からは飛ばす
終端として扱う	すでに記録にある場所なら、そこから先へ進まない

記録しないと、同じ場所をぐるぐる回って終わりません。 スライドパズルのように状態が戻り得る題材では、ここが欠かせません。

使う場面

場面	向くほう
最短の手数を知りたい	幅優先探索
道があるかどうかだけ知りたい	どちらでもよい
全部のつながりを調べたい	どちらでもよい
メモリが限られている	深さ優先探索
深さが非常に深い、または無限に続き得る	幅優先探索（深さ優先は戻ってこなくなる）

処理の形

幅優先探索の流れ

手順	すること
1	始めの点をキューに入れる
2	キューから1つ取り出す
3	そこから行ける先を作り、ゴールかどうかを調べる
4	調べ済みでなければキューに入れ、記録に加える
5	キューが空になるまで2〜4を繰り返す

キューが空になったら、ゴールへ行く道が無いという結論になります。

試験ではこう出る

科目A（旧・午前）では、使う入れ物が問われます。幅優先はキュー、深さ優先はスタックです。

最短を保証するかも出ます。幅優先は保証し、深さ優先は保証しません。

午後や応用情報（プログラミング）では、擬似言語で書かれた幅優先探索を読む形で出ます。キューへの出し入れ、調べ済みの記録、ゴールの判定が空欄になります。

図の中のノードの番号を順に追うと、どの順で作られたかが分かります。 同じ深さのものが続けて並ぶのが幅優先探索の特徴です。

ミニクイズ

幅優先探索で、次に調べる対象を取り出すために使うデータ構造はどれか。

正解は 2番：キュー

幅優先探索は、近いところから順に調べるので、先に見つけたものを先に取り出す必要があります。そのため先入先出のキューを使います。スタックは後入先出なので、最後に見つけたところから進む深さ優先探索に向きます。ハッシュ表は値から位置を求める仕組み、二分探索木は大小で枝分かれさせた木で、どちらも探索の順序を決める入れ物ではありません。

間違えた用語の復習リストを見る →

この分野をまとめて解く → アルゴリズムとプログラミングのミニテスト（全44問）

最終更新：2026-11-09