探索木のたどり方には大きく2つの流儀があります。そのひとつ、幅優先探索は「出発点に近いところから、しらみつぶしに輪を広げていく」方式です。最短の解を必ず見つけられる代わりに、メモリを大量に使う——この長所と短所のセットが試験の頻出ポイントです。
📖 ひと言でいうと
幅優先探索とは、探索木を出発点に近いノードから順に、同じ深さをすべて調べてから次の深さへ進む探索手法です。たとえるなら、池に石を落としたときの波紋のように、スタート地点から近い順に同心円状に調べる範囲を広げていくイメージです。「横に広げてから下りる」動きから横型探索とも呼ばれます。
🖼 1枚でわかる幅優先探索
📘 対策テキストの説明
出発点に近いノード（探索木の各要素）順に検索する。出発点から遠いノードほど検索は後回しになる。最短距離でゴールにたどり着く解を見つけることができる。探索の途中で立ち寄ったノードをすべて記憶しておく必要がありメモリが多く必要となる。
この短い説明に、試験で問われる要素が全部詰まっています。①調べる順番は「出発点に近い順」。②その結果として最短距離の解を見つけられるという保証がある。③引き換えに、立ち寄ったノードをすべて記憶するのでメモリを多く消費する。「最短の解が見つかる=長所」と「メモリ大=短所」を必ずワンセットで覚えてください。
🔍 しっかり理解する
なぜ「近い順」だと最短の解が見つかるのか
幅優先探索は、深さ1のノードをすべて調べ終えてから深さ2へ、深さ2をすべて調べてから深さ3へ、と進みます。つまり「出発点から1手で行ける場所」「2手で行ける場所」……と、手数の少ない順に調べているのです。
この順番で探すと、ゴールに最初に到達した瞬間、それより少ない手数の候補はすべて調べ尽くした後だと保証されます。だから「最初に見つけた解=最短の解」になるのです。運や探索の順序に左右されず、確実に最短解が得られる——これが幅優先探索の最大の強みです。
なぜメモリを多く使うのか
近い順に調べるためには、「次に調べる予定のノードの待ち行列」を管理し、探索の途中で立ち寄ったノードを記憶し続ける必要があります。ところが探索木は深さが1増えるごとにノード数が何倍にも増えます。たとえば各ノードから3本ずつ枝が伸びる木なら、深さ10の階層だけで約5万9千ノード、深さ15では約1,400万ノードにもなります。
同じ深さのノードをまとめて抱えながら進む幅優先探索は、この膨れ上がった階層を丸ごと記憶することになり、メモリ消費が深刻になります。ここが、1本道の経路だけ覚えればよい深さ優先探索との決定的な違いです。
「待ち行列」で動く——実現のイメージ
幅優先探索の「近い順」は、先に見つけたものから先に処理する待ち行列（キュー）で実現できます。手順はこうです。まず出発点を行列に入れます。行列の先頭からノードを1つ取り出して調べ、そのノードから枝でつながる未訪問のノードを行列の最後尾に追加します。これをゴールが見つかるまで繰り返すだけです。
先頭から取り出し、最後尾に追加する——この単純なルールにより、浅いノードが必ず深いノードより先に処理され、自動的に「出発点に近い順」が守られます。銀行の窓口で番号札の順に呼ばれるのと同じ仕組みで、「早く見つかったノード（=出発点に近いノード）ほど早く調べられる」と考えるとイメージしやすいでしょう。逆に深さ優先探索は「後から見つけたものを先に処理する」積み上げ方式で動く、という対応関係も知っておくと理解が深まります。
深さ優先探索との対比
- 出発点に近い順・同じ深さを横に調べる
- 最短距離の解を必ず発見できる
- 立ち寄ったノードを全部記憶→メモリ大
- 1本の枝を行き止まりまで縦に進む
- 最短の解が見つかるとは限らない(運任せの面)
- メモリ使用量は少なくて済む
どちらが優れているかは一概に言えず、「最短の解が欲しいなら幅優先、メモリを節約したいなら深さ優先」という使い分けの関係にあります。試験ではこの表裏の関係が最大の問われどころです。
💡 具体例で考える
駅の乗り換え案内で「乗り換え回数が最も少ない経路」を探す場面を考えましょう。出発駅を根として、「1回の乗車で行ける駅」をまず全部挙げ、次に「2回の乗車で行ける駅」を挙げ……と近い順に調べていくのが幅優先探索です。目的の駅が初めて現れた時点で、それが最少乗車回数の経路だと確定します。
逆に、適当に1つの路線を終点までたどり、ダメなら戻って別の路線を試す方式（深さ優先的なやり方）でも目的駅にはいつか到達できますが、最初に見つかった経路が遠回りである可能性があります。「確実に最短が欲しい場面では近い順に調べる」という幅優先探索の価値がよくわかる例です。
ただし、路線網が巨大になると「1回で行ける駅」「2回で行ける駅」のリストはどんどん膨らみます。全国の鉄道網を対象にすれば、抱えるべき駅の数は階層が進むごとに何倍にも増えていき、これがそのまま「メモリが多く必要」という短所の実感になります。長所と短所が同じ仕組み（近い順のしらみつぶし）から生まれている点まで含めて理解しておきましょう。
⚠️ よくある誤解・紛らわしい用語
- 「速い探索」ではない — 幅優先探索の長所は「最短の解が見つかる」ことであって、探索の計算が速いわけではありません。しらみつぶしなので調べるノード数はむしろ多くなりがちです。
- メモリの長短を逆に覚えない — 「メモリが少なくて済む」のは深さ優先探索です。幅優先探索は「すべて記憶するのでメモリ大」。ここを入れ替えた誤答選択肢が定番です。
- 別名の対応 — 幅優先=横型、深さ優先=縦型です。「幅=横」とイメージで結びつけておきましょう。
- 最短の保証条件 — ここでいう最短は「探索木の深さ（手数）が最小」という意味です。枝ごとに異なるコストがある問題では、単純な幅優先探索だけでは最小コストの保証はできません（厳密には別の工夫が必要です）。
📝 試験でのポイント
- 「最短距離でゴールにたどり着く解を見つけられるが、メモリが多く必要な探索は？」という長所・短所セットでの出題が最有力です。
- 深さ優先探索と特徴を入れ替えた誤文（「幅優先はメモリが少ない」等）の正誤判定に備えましょう。
- 「横型探索」という別名から幅優先探索を選ばせるパターンも想定されます。
- 「出発点から遠いノードほど後回し」という調べる順番の記述も、そのまま正誤問題の材料になります。
📚 まとめ
- 幅優先探索は、探索木を出発点に近いノードから順に調べる手法で、横型探索とも呼ばれます。
- 手数の少ない順に調べるため、最初に見つけた解が必ず最短距離の解になります。
- 引き換えに、立ち寄ったノードをすべて記憶する必要があり、メモリ消費が大きいのが短所です。
- 深さ優先探索と長所・短所がちょうど逆の関係にあり、この対比が試験の最重要ポイントです。
