幅優先探索 (G検定)

1. 定義と概要

幅優先探索（breadth-first search、頭文字を取ってBFSとも呼ばれます）とは、探索木やグラフにおいて、開始ノードに近い浅い階層のノードから順にすべて調べ尽くしてから次に深い階層へ進む探索手法です。同じ深さのノード（探索木を構成する各地点・状態を表す点）を、横方向にしらみつぶしに調べていきます。

実装では、次に調べるノードを一時的に保持するために待ち行列（キュー）を使います。待ち行列（キュー）とは、先に入れたものを先に取り出す並べ方のことで、先入れ先出し=FIFOとも呼ばれます。

具体的な手順としては、開始ノードをキューへ入れ、キューから取り出したノードの隣接ノードを順にキューへ追加する処理を、探索が終わるまで繰り返します。取り出す順番と入れる順番が同じになるため、開始ノードに近いノードほど先に処理されます。この繰り返しによって、近い階層から遠い階層へ順序よく調べ尽くしていきます。

迷路の最短路探索やパズルの状態遷移、ゲームの手順探索といった問題は、選択肢や状態の移り変わりを探索木で表すことで機械的に扱えます。従来はこうした探索木をどのノードからどの順序で調べるかが工夫の対象とされ、幅優先探索と深さ優先探索がその代表的な2手法として整理されてきました。

幅優先探索は、開始ノードから近い順に階層的に調べていく方式にあたり、探索対象が広がるほど階層ごとの処理の仕方が結果を左右します。階層が深くなるほど1階層あたりのノードが増えていくため、どこまで広げて調べるかが実用上の勘どころになります。

2. 試験対策ポイント

理解するうえで中心になるのは、エッジの重みが等しい（移動コストが均一な）グラフにおいて、幅優先探索が開始ノードから目的ノードまでの最短経路を必ず発見できるという保証です。同じ深さのノードを一段ずつ確実に調べ尽くすため、目的ノードへ最初にたどり着いた経路がそのまま最短経路になります。これは幅優先探索の最大の利点として扱われます。

一方で、探索が進むにつれて各階層のノードの情報をキューにすべて保持するため、メモリ使用量が大きくなりやすいという制約があります。この利点と制約はセットで整理しておきたいポイントです。

実装で使うデータ構造にも違いがあり、幅優先探索は待ち行列（キュー、FIFO）を用いるのに対し、深さ優先探索はスタック（後に入れたものを先に取り出す並べ方、LIFO）または再帰処理を用います。この使用するデータ構造の違いも、幅優先探索と深さ優先探索を区別する観点として扱われます。

深さ優先探索は幅優先探索に比べてメモリ使用量が少なく済む一方、最初に見つかる解が必ずしも最短経路とは限らないというトレードオフの関係にあります。深さ優先探索そのものの仕組みは別記事で扱います。

3. 関連概念との比較・相違点

深さ優先探索との最大の違いは、メモリ使用量と最短経路の保証、そして使用するデータ構造という3点にあります。幅優先探索は探索途中の各階層のノードをキューに保持していくため、メモリ使用量が大きくなりやすい一方、開始ノードから目的ノードまでの最短経路を必ず発見できるという保証があります。

深さ優先探索は、一つの経路を行き止まりまで進んでから後戻りして別の経路を調べる方式です。保持するのは今たどっている一本の経路の情報だけのため、メモリ使用量は幅優先探索より少なく済みますが、最初に見つかる解が最短経路とは限りません。

両手法の対応関係を観点ごとに並べると、次のようになります。

観点	幅優先探索	深さ優先探索
調べる順序	浅い階層から同じ深さを調べ尽くして次の深さへ進む	一つの経路を行き止まりまで進んでから後戻りする
メモリ使用量	各階層のノードを保持するため大きくなりやすい	たどっている一本の経路分で済み少なくなる
最短経路の保証	重みが等しいグラフでは必ず最短経路を発見できる	最初に見つかる解が最短経路とは限らない
使用するデータ構造	待ち行列（キュー、FIFO）	スタック（LIFO）または再帰処理

この2手法は、同じ探索木を対象にしていても、調べる順序も保持する情報量もまったく異なります。

解を確実に最短で求めたいか、限られたメモリで探索したいかという目的に応じて、幅優先探索と深さ優先探索は使い分けられる関係にあります。目的と手法の対応づけを理解するうえでの中心的な論点であり、それぞれの利点と制約を対にして整理しておくことが手がかりになります。

4. ビジネス・実務での活用シナリオ

SNS・ネットワークサービスの分野では、ユーザー同士のつながりを解析する際に幅優先探索が使われます。自分を起点に1段階先の友人、その友人の友人へと階層を広げて探索することで、自分と相手が何親等先でつながっているかを判定する仕組みに応用されています。階層を1つずつ確実に調べ尽くしていく幅優先探索の性質を生かすことで、遠回りをせずに最も近いつながりを数えられます。

地図・乗換案内の分野でも活用されています。駅間の移動区間を均等なコストとみなせる場面で、出発地から目的地までの最少乗換回数や最少経由地点数を階層的に求める処理に幅優先探索が使われます。移動コストが均一な区間では最短経路が必ず見つかるという幅優先探索の保証が、案内の正確さを支えています。

ネットワーク通信の分野では、近隣のノードから順に接続状況を確認していくことで、パケット（通信データの小さなかたまり）が宛先に届くまでの経路を決定する仕組みに幅優先探索が応用されています。近い経路から順に確かめていく進め方は、遠回りの経路を避けて通信の効率を保つことにつながります。

5. 要点まとめ

• 幅優先探索は探索木の同じ深さのノードをすべて調べてから次の深さへ進む手法で、待ち行列（キュー）を使って実装します。
• 開始ノードから目的ノードまでの最短経路を必ず発見できる一方、各階層のノードを保持するためメモリ使用量が大きくなります。
• 深さ優先探索とは、メモリ使用量・最短経路の保証・使用するデータ構造（キューかスタックか）の3点で対比される関係にあります。

6. 確認問題