幅優先探索

2025年10月21日

“`

幅優先探索

英語表記: Breadth-First Search

概要

幅優先探索（BFS）は、グラフやツリー構造を持つデータの中から、目的の要素や最短経路を見つけ出すための基本的な探索アルゴリズムの一つです。この探索手法は、現在地から近いノード（隣接ノード）を優先的に調べ、探索範囲を層状に広げていくのが最大の特徴です。そして、この「近いものから順に」という処理順序を厳密に守るために、データ構造の中でも特にキュー（Queue）の機能が必須の要素として利用されています。そのため、幅優先探索は「データ構造（リスト, スタック, キュー, ツリー）」という大きな分類の中で、「キュー」の具体的な「応用例」として非常に重要な位置を占めているのです。

詳細解説

幅優先探索の最大の目的は、出発点から最も近い要素を確実に見つけ出すこと、すなわち最短経路を探索することにあります。ツリー構造やネットワーク（グラフ）において、階層（レベル）ごとに探索を進めるため、深さ方向ではなく、横方向（幅）に広がっていくのが特徴です。

なぜキューが必要なのか

幅優先探索が「キューの応用例」として分類される理由は、その動作原理そのものにあります。キューは「先入れ先出し（FIFO：First-In, First-Out）」の原則に従うデータ構造です。

探索開始: まず、探索を開始するノード（始点）をキューに入れます。
ノードの取り出し: キューの先頭にあるノードを取り出します（これが現在探索中のノードです）。
隣接ノードの調査と格納: 取り出したノードに隣接している、まだ訪問していないすべてのノードを見つけ出し、それらをキューの末尾に追加していきます。
繰り返し: キューが空になるまで、ステップ2と3を繰り返します。

このように、先にキューに入ったノード（つまり、始点から近いノード）が先に処理され、その次に近いノード群がその後に処理される、という流れが生まれます。このFIFOの性質が、探索を「レベル順」に進めることを保証し、結果として最短経路を確実に見つけ出すことを可能にしているのです。もしここでキューではなくスタック（LIFO）を使ってしまうと、探索は深さ方向に偏ってしまい、幅優先探索の特性は失われてしまいます。したがって、幅優先探索はキューの存在なしには成り立たない、まさにキューの代表的な応用例と言えるでしょう。

処理のイメージ

幅優先探索は、まるで水面に小石を投げたときに広がる波紋のように探索範囲を広げていきます。

レベル0: 始点（キューに入れる）
レベル1: 始点の隣接ノード群（キューから始点を取り出し、隣接ノードをすべてキューに入れる）
レベル2: レベル1のノード群の隣接ノード群（レベル1のノードを順番に取り出し、その隣接ノードをキューに入れる）

この手順により、レベル1のノードの探索が終わってから初めてレベル2のノードの探索が始まるため、最短経路が保証されるわけです。最短経路を求める問題では、この性質が非常に頼りになりますね。

具体例・活用シーン

幅優先探索は、その最短経路を見つけるという強みから、私たちの身の回りにある多くのシステムで活用されています。

1. ナビゲーションシステム・経路探索

カーナビゲーションや地図アプリで、出発地から目的地までの最短の道のり（通過する交差点や道路の数が最も少ないルート）を計算する際に利用されます。

具体例: ある交差点（ノード）から出発し、隣接する交差点（エッジ）を順にキューに入れながら探索することで、無駄なく最短のルートを特定できます。これは、データ構造としてのグラフ（交差点＝ノード、道路＝エッジ）を、キューを用いて効率的に探索している典型例です。

2. ソーシャルネットワークの繋がり

SNS（ソーシャルネットワーキングサービス）において、「知り合いの知り合い」という形で、あるユーザーから他のユーザーまでの最短の繋がり（ホップ数）を計算する際にも幅優先探索が使われます。

具体例: あなたを始点とし、友達（レベル1）をキューに入れ、次に友達の友達（レベル2）をキューに入れ、と進むことで、「六次の隔たり」のような最短距離を効率的に見つけ出します。

アナロジー：火事の延焼

幅優先探索の動作を理解するための最も分かりやすい比喩は、「火事の延焼」です。

ある一点で火事（始点）が発生したと想像してください。火は、まず発生源に最も近い家々（レベル1）に同時に燃え広がります。レベル1の家がすべて燃え尽きる（探索される）と、次にそれらに隣接する家々（レベル2）へと広がっていきます。この延焼の順序は、発生源から近い順に進むため、最も早く火が到達する家を特定するのに適しています。

この火事の例では、「次に燃えるべき家」を管理するリストが、まさにキューの役割を果たしていると考えると分かりやすいです。先に火がつく運命にある家（先にキューに入ったノード）が、先に処理される（延焼する）というわけです。幅優先探索は、このように「近い」という基準を厳格に守って探索を進める、非常に律儀なアルゴリズムだと言えますね。

資格試験向けチェックポイント

日本のIT資格試験（ITパスポート、基本情報技術者、応用情報技術者）では、探索アルゴリズムは頻出テーマです。特に幅優先探索は、対となる「深さ優先探索（DFS）」との比較を通じて出題されることがほとんどです。

典型的な出題パターンとヒント

データ構造の対応:
- 「幅優先探索が使用するデータ構造として正しいものはどれか」という問いに対して、迷わず「キュー」を選べるようにしておきましょう。これが、このアルゴリズムがキューの応用例として学習される最大の理由です。
最短経路:
- 「最短のノード数で到達できる経路を求めるのに適した探索アルゴリズムはどれか」という問は、BFSの最も得意とする分野を示しています。グラフやツリーの探索で最短性を問われたら、BFSを思い出してください。
探索順序のトレース:
- 特定のグラフ構造が与えられ、始点から探索を開始した場合のノードの訪問順序を問う問題が出ます。キューの動作（FIFO）をシミュレーションし、レベルごとにノードが処理されることを確認しながら順序を追う練習が必要です。
計算量:
- 応用情報技術者試験では、計算量が出題されることがあります。BFSの計算量は一般に $O(V+E)$ で表されます（Vは頂点数、Eは辺数）。すべての頂点と辺を一度ずつチェックするため、非常に効率的です。