BFS (幅優先探索)（BFS: ビーエフエス）

2025年10月20日

BFS (幅優先探索)（BFS: ビーエフエス）

英語表記: BFS (Breadth-First Search)

概要

BFS（幅優先探索）は、「アルゴリズムと計算量」の分野、特に「グラフアルゴリズム」における最も基本的な「基本探索」手法の一つです。これは、グラフの探索開始点（ノード）から見て、近いノードを優先的に、つまり同心円状に「幅広く」探索を進めていくアルゴリズムです。重み付けされていないグラフにおいて、スタート地点から任意のノードまでの最短経路を見つける際に非常に強力なツールとなります。

詳細解説

BFSは、グラフ構造を効率的に、かつ体系的に探索するために設計されています。このアルゴリズムを理解することは、「グラフアルゴリズム」の基礎を固める上で欠かせません。

目的と動作原理

BFSの最大の目的は、探索の深さよりも「幅」を優先することにあります。具体的には、スタート地点から距離1のノードをすべて探索し終えてから、次に距離2のノード群へ移り、さらに距離3へと進む、というように、レベル（深さ）ごとに探索を進めます。この特性から、最短経路を発見するのに適しているのです。もし目的地がスタート地点から最短のルートで見つかれば、それは必ずBFSが最初に発見するルートとなります。これは非常に合理的で、素晴らしい特性ですよね。

主要なコンポーネント：キューの利用

BFSが「幅優先」を実現するために利用する最も重要なデータ構造はキュー（Queue、待ち行列）です。キューは、FIFO (First-In, First-Out)、つまり「最初に入れたものが最初に出る」という特性を持っています。

初期化: 探索開始ノードをキューに入れ、探索済みとしてマークします。
ノードの取り出し: キューの先頭からノードを取り出します。
隣接ノードの調査: 取り出したノードに隣接する、まだ探索されていないノードをすべて見つけます。
キューへの追加: 見つけた隣接ノードをすべてキューの末尾に追加し、探索済みとしてマークします。
反復: キューが空になるまで手順2〜4を繰り返します。

このように、あるノードから隣接するすべてのノードを「同時に」キューに入れることで、それらのノードが「同じ深さ」として扱われ、次に処理される順番が保証されるわけです。

タクソノミーとの関連性

この探索手法は、なぜ「アルゴリズムと計算量」→「グラフアルゴリズム」→「基本探索」という分類に入るのでしょうか。

アルゴリズムと計算量: BFSの効率性は計算量で評価されます。グラフの頂点（ノード）の数をV、辺（エッジ）の数をEとしたとき、BFSの計算量は通常 $O(V+E)$ で表現されます。これは、すべての頂点を一度ずつ訪問し、すべての辺を一度ずつチェックするだけで済むため、非常に効率的であるとされています。この効率性が、この分野でBFSが重要視される理由です。
グラフアルゴリズム: BFSは、ネットワークや地図、人間関係など、ノードとエッジで表現される「グラフ」構造に特化した処理です。グラフの連結性（すべて繋がっているか）や最短経路を調べるなど、グラフに関する様々な問題の基礎となります。
基本探索: グラフ探索の基本中の基本であり、対照的な概念であるDFS（深さ優先探索）と並んで、すべての高度なグラフアルゴリズムの出発点となります。この二つの基本探索を理解せずに、応用的なグラフ問題を解くことはできません。

具体例・活用シーン

BFSの動作は、日常的な現象やシミュレーションに例えると非常に分かりやすく理解できます。

1. 水面に広がる波紋（アナロジー）

BFSの動作を理解するのに最も適したアナロジーは、「水面に石を投げ入れたときに広がる波紋」です。

スタート地点: 石が落ちた中心点です。
深さ1: 最初に広がる小さな波の輪です。
深さ2: その外側に広がる次の輪です。

水面の波紋は、中心点から「幅広く」「均等に」外側へ広がっていきます。BFSもこれと同じで、スタート地点から等距離にあるノード群を順番に処理していくのです。もしゴールが波紋の途中にあれば、波紋が到達した瞬間、それが最短ルートであることが一目で分かります。

2. SNSにおける最短の知り合いルート

ソーシャルネットワーキングサービス（SNS）で、自分（スタートノード）と、遠くにいる有名人（ゴールノード）が何人の友人を介して繋がっているかを探る際にも、BFSの考え方が使えます。

レベル1: 自分の直接の友人たち。
レベル2: 友人の友人たち（自分とは2ホップ離れている）。
レベル3: 友人の友人の友人たち（自分とは3ホップ離れている）。

BFSを使えば、レベル1から順番に探索するため、「最短で何ホップで繋がっているか」を確実に、そして効率的に見つけ出すことができます。

3. 迷路の最短脱出ルート

重みがない普通の迷路において、スタート地点からゴール地点までの最短の歩数を求めたい場合、BFSは最適です。もしDFS（深さ優先探索）を使うと、行き止まりにぶつかるまで深く進んでしまうため、遠回りになる可能性が高いです。しかし、BFSを使えば、すべての交差点から等しく幅広く探索するため、最初に見つけたゴールへのルートが、壁や障害物を考慮した上での最短ルートとなります。これは、カーナビゲーションシステムにおける最短経路探索の基礎技術の一つでもあり、私たちの生活を支えている重要なアルゴリズムだと感じます。

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

IT資格試験、特に基本情報技術者試験や応用情報技術者試験では、「アルゴリズムと計算量」の知識として、BFSの理解度が問われます。

| 試験で問われるポイント | 解説と対策 |
| :— | :— |
| DFS（深さ優先探索）との対比 | BFSは「キュー」を使用し、幅広く探索するのに対し、DFSは「スタック」を使用し、深く探索します。この使用するデータ構造の違いと、それによって生じる探索パターンの違いを必ず理解してください。 |
| 最短経路問題への適用 | 重みなしグラフ（辺に移動コストが設定されていないグラフ）において、BFSは最短経路を求めるアルゴリズムとして機能します。この適用範囲が頻出です。ダイクストラ法やA探索法との違い（それらは重み付きグラフに対応）も把握しておくと応用情報技術者試験対策になります。 |
| 計算量 O(V+E) の理解 | 頂点数 V、辺数 E のグラフにおける計算量 $O(V+E)$ の意味を覚えておきましょう。これは「すべての頂点と辺をせいぜい一度ずつ処理する」という意味であり、非常に効率的であることを示しています。 |
| 探索ステップの追跡 | 特定のグラフ図が提示され、「BFSで探索した場合、ノードが訪問される順番を答えよ」という問題が出題されます。キューへの追加・取り出しのルールに従って、探索の手順を正確に追えるように練習が必要です。 |
| タクソノミー文脈での位置づけ* | BFSが「基本探索」であり、より複雑な「グラフアルゴリズム」の土台となっているという構造的な理解が問われることがあります。 |