C++のSTLを活用したBFS（幅優先探索）の実装方法 ― 競技プログラミング向け解説

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

競技プログラミングでは、いかに速く問題を解けるかが重要になります。C++のSTL（標準ライブラリ）を活用すれば、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 に追加する
    que が空でない間、以下を繰り返す
        que から要素を取り出し、u に代入する
        頂点 u を表示する
        u に隣接するすべての頂点 v に対して、以下を実行する
            vertices[i] が未訪問であれば
                vertices[i] を「一時的に訪問済み」としてマークする
                v をキューに追加する
            マーク処理を終える
        処理終了
        u を「完全に訪問済み」としてマークする
    繰り返し終了
End

C++での実装例

#include<iostream>
#include<queue>
#define NODE 6
using namespace std;
class node {
    public:
        int val;
        int state; //状態
};
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