グラフの幅優先探索(BFS)とは?仕組み・アルゴリズム・C++実装例をわかりやすく解説

幅優先探索(BFS)とは

幅優先探索(Breadth First Search:BFS)は、与えられたグラフのすべてのノード(頂点)を訪問するために用いられる探索アルゴリズムです。この手法では、まず1つのノードを選択し、その隣接ノードを1つずつ順番に訪問していきます。すべての隣接頂点の処理が完了したら、次の頂点へ移動し、同様にその隣接頂点を順に確認していきます。

BFSを実装する際には、キュー(Queue)データ構造が必要です。隣接する頂点をすべてキューに追加し、それらの処理が完了したらキューから1つ取り出し、その頂点を起点として再び探索を続けます。

また、グラフにはサイクル(閉路)が含まれることがあるため、配列を用いて各ノードが「既に訪問済みかどうか」を記録し、同じノードを何度も訪問しないように制御します。

入力と出力

入力 − グラフの隣接行列

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)

入力 − 頂点のリスト、および開始頂点。

出力 − グラフが連結であれば、すべてのノードを走査します。

Begin
　　空のキュー que を定義する
　　最初に、すべてのノードの状態を「未訪問」としてマークする
　　開始頂点をキュー que に追加する
　　キューが空でない間、以下を繰り返す
　　　　キューから要素を取り出し、u に代入する
　　　　頂点 u を表示する
　　　　u に隣接するすべての頂点 i に対して
　　　　　　もし vertices[i] が未訪問ならば
　　　　　　　　vertices[i] を一時的に訪問済みとしてマークする
　　　　　　　　v をキューに追加する
　　　　　　マーク処理終了
　　　　繰り返し終了
　　　　u を完全に訪問済みとしてマークする
　　繰り返し終了
End

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)は、開始頂点から近いノードから順に層状に広がっていく探索手法であり、最短経路探索や連結判定など、さまざまなグラフ問題の基礎となる重要なアルゴリズムです。実装にはキューを利用し、訪問済みフラグによってサイクルへの対応を行う点がポイントになります。