BFS(ビーエフエス)とは | 意味や読み方など丁寧でわかりやすい用語解説

BFSは「Breadth-First Search」の略で、日本語では「幅優先探索」と訳される、グラフやツリー構造の探索アルゴリズムの一つである。主に、グラフの特定の開始ノードから到達可能な全てのノードを効率的に探索したり、重みを持たないグラフにおいて最短経路を見つけたりするために用いられる。システムエンジニアリングの分野では、ネットワークの経路探索、ソーシャルネットワークにおける友人関係の分析、ウェブクローラーの巡回ロジック、ゲームのAIにおける最短ルート探索など、多岐にわたる問題解決に応用されている。このアルゴリズムの基本的な考え方は、深さ優先探索（DFS）がなるべく深く進むのに対し、開始点から近いノードを「幅広く」探索していく点にある。

BFSは、探索を開始するノードを起点として、まずそのノードに直接つながる全てのノードを探索する。次に、それらのノードに直接つながるまだ探索されていないノードを全て探索する、というように、開始点からの距離が等しいノードの層（レベル）ごとに探索を進めていく。この「層」ごとの探索という特性が、BFSの最も重要な動作原理であり、多くの応用の基盤となっている。

このアルゴリズムを実現するために、キュー（待ち行列）というデータ構造が不可欠である。キューは「First-In, First-Out」（FIFO、先入れ先出し）の原則に従って要素を管理するデータ構造で、最初に入れたものが最初に処理される。BFSでは、探索すべきノードをこのキューに入れて管理する。具体的には、まず探索を開始するノードをキューに入れ、同時にそのノードを「訪問済み」として記録する。その後、キューが空になるまで以下の操作を繰り返す。まず、キューからノードを一つ取り出す。取り出したノードに直接隣接する全てのノードについて確認し、もしその隣接ノードがまだ訪問済みでなければ、その隣接ノードをキューに追加し、「訪問済み」として記録する。このプロセスにより、開始ノードから近いノードが優先的にキューに入り、優先的に処理されるため、自然と層ごとの探索が実現されるのである。

「訪問済み」という状態を記録することは、非常に重要である。これは、同じノードを複数回探索したり、グラフの循環構造（サイクル）がある場合に無限ループに陥ることを防ぐためである。通常、ブール値の配列やハッシュテーブルなどを用いて、各ノードが訪問されたかどうかを管理する。一度訪問されたノードは、再び探索の対象とはしない。これにより、探索の効率性を保ち、正しい結果を保証できる。

BFSの最も強力な特性の一つは、重みを持たないグラフにおいて、開始ノードから他の任意のノードまでの「最短経路」（辺の数が最小の経路）を発見できる点にある。これは、キューの特性と層ごとの探索が保証する。例えば、開始ノードから1辺で到達できるノードが全て探索された後に、2辺で到達できるノードが探索される。したがって、あるノードに初めて到達した経路が、そのノードへの最短経路となることが保証されるのである。これは、迷路の最短ルートを見つけたり、ネットワーク上での最小ホップ数での接続を調べたりする際に非常に有用である。

BFSの応用例は多岐にわたる。ウェブクローラーは、あるウェブページからリンクをたどって次のページへと移動し、インターネット全体を巡回するが、この際にBFSの考え方を用いて、起点となるページから距離の近いページを優先的に巡回することで、効率的に情報を収集できる。ソーシャルネットワークにおける「友人の友人」を探すような機能も、各ユーザーをノード、友人関係を辺と見立てることで、BFSによって効率的に実装可能である。また、グラフがいくつの連結成分で構成されているかを調べたり、二部グラフの判定を行ったりする際にもBFSが利用される。

計算量に関しては、BFSの時間計算量はO(V + E)で表現される。ここで、Vはグラフのノード（頂点）の数、Eはグラフのエッジ（辺）の数である。これは、全てのノードと全ての辺を最大で一度ずつ調べるため、非常に効率的であると言える。空間計算量はO(V)となる。最悪の場合、キューにグラフの全てのノードを格納する必要があるためである。

まとめると、BFSはグラフ探索において、開始点から近いノードから順に層状に探索を進める強力なアルゴリズムである。キューというデータ構造を巧みに利用することで、効率的に全ノードを探索し、重みなしグラフにおける最短経路を発見できる。その原理と応用範囲の広さから、システムエンジニアが理解すべき基本的なアルゴリズムの一つである。ただし、辺に重みがあるグラフにおける最短経路問題には適さないため、その場合はダイクストラ法などの別のアルゴリズムを検討する必要がある。