グラフの幅優先探索（BFS）とは？仕組みとC++実装例を徹底解説

幅優先探索（Breadth First Search：BFS）は、与えられたグラフのすべてのノードを訪問するための基本的なグラフ探索アルゴリズムです。この探索手法では、まず1つのノードを選択し、その隣接ノードを1つずつ順番に訪問していきます。ある頂点の隣接頂点をすべて処理し終えると、次の頂点へ移動し、同様にその隣接頂点を確認していくのが特徴です。

BFSの仕組みとキューの役割

BFSを実装するには、キュー（Queue）というデータ構造が必要です。探索対象となる隣接頂点はすべてキューに追加され、現在の頂点の隣接頂点の処理が完了すると、キューの先頭から要素を1つ取り出し、その頂点から再び探索を続けます。この「先入れ先出し（FIFO）」の性質により、開始点に近いノードから順に幅方向へ探索が広がっていきます。

また、グラフにはサイクル（閉路）が含まれることがあります。同じノードを何度も訪問して無限ループに陥るのを防ぐため、各ノードがすでに訪問済みかどうかを記録する配列を用いて状態を管理します。

入力と出力

入力:
グラフの隣接行列

      A B C D E F
  A   0 1 1 1 0 0
  B   1 0 0 1 1 0
  C   1 0 0 1 0 1
  D   1 1 1 0 1 1
  E   0 1 0 1 0 1
  F   0 0 1 1 1 0

出力:
BFS Traversal: B A D E C F

アルゴリズムの手順

bfs(vertices, start)

入力 − 頂点のリストと、探索を開始する頂点。

出力 − グラフが連結である場合、すべてのノードを巡回します。

処理の流れは以下の通りです。

1. 空のキュー que を定義する。
2. 最初に、すべてのノードの状態を「未訪問」に設定する。
3. 開始頂点をキューに追加する。
4. キューが空でない間、以下を繰り返す。
   • キューから要素を取り出し、変数 u に代入して表示する。
   • u に隣接するすべての頂点 i について、未訪問であれば「一時的に訪問済み」とマークし、キューに追加する。
   • u を「完全に訪問済み」とマークする。

C++による実装例

以下は、隣接行列で表現されたグラフに対してBFSを実行するC++プログラムの例です。

#include<iostream>
#include<queue>
#define NODE 6
using namespace std;

typedef struct node {
    int val;
    int state;     // 状態（0: 未訪問, 1: 訪問中, 2: 完了）
}node;

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0, 0},
    {1, 0, 0, 1, 1, 0},
    {1, 0, 0, 1, 0, 1},
    {1, 1, 1, 0, 1, 1},
    {0, 1, 0, 1, 0, 1},
    {0, 0, 1, 1, 1, 0}
};

void bfs(node *vert, node s) {
    node u;
    int i, j;
    queue<node> que;

    for(i = 0; i<NODE; i++) {
        vert[i].state = 0;     // 未訪問に初期化
    }

    vert[s.val].state = 1;     // 開始ノードを訪問済みにする
    que.push(s);               // 開始ノードをキューに挿入

    while(!que.empty()) {
        u = que.front();       // キューから取り出して表示
        que.pop();
        cout << char(u.val+'A') << " ";

        for(i = 0; i<NODE; i++) {
            if(graph[i][u.val]) {
                // ノードが未訪問の場合
                if(vert[i].state == 0) {
                    vert[i].state = 1;
                    que.push(vert[i]);
                }
            }
        }
        u.state = 2;           // ノード u の探索完了
    }
}

int main() {
    node vertices[NODE];
    node start;
    char s;

    for(int i = 0; i<NODE; i++) {
        vertices[i].val = i;
    }

    s = 'B';                   // 開始頂点は B
    start.val = s-'A';
    cout << "BFS Traversal: ";
    bfs(vertices, start);
    cout << endl;
}

実行結果

BFS Traversal: B A D E C F

BFSの計算量

隣接行列を用いたBFSの計算量は、頂点数を V、辺数を E とすると O(V²) となります。一方、隣接リストを用いた場合は O(V + E) で実行でき、疎なグラフではより効率的です。最短経路問題やネットワークの到達可能性判定など、さまざまな場面で活用される重要なアルゴリズムなので、ぜひマスターしておきましょう。