C++でベクトルとキューを使ったBFS（幅優先探索）の実装 ― CLRSのアルゴリズムに沿って解説

CLRS（『Introduction to Algorithms』）では、BFS（幅優先探索）のアルゴリズムがベクトルとキューを用いて記述されています。ここでは、そのアルゴリズムをC++のSTL（標準テンプレートライブラリ）を使って実装する方法を解説します。まず、元となるアルゴリズムの擬似コードを確認しましょう。

BFSのアルゴリズム

各頂点には3つの属性があります。color（探索状態）、d（始点からの距離）、p（親頂点）です。色は「白＝未訪問」「グレー＝発見済みだが処理中」「黒＝処理完了」を表します。

BFS(G, s) −
begin
    for each vertex u in G.V - {s}, do
        u.color := white
        u.d := infinity
        u.p := NIL
    done
    s.color := green
    s.d := 0
    s.p := NIL
    Q := NULL
    insert s into Q
    while Q is not null, do
        u = delete from Q
        for each v in adjacent to u, do
            if v.color = white
                v.color := green
                v.d := u.d + 1
                v.p := u
                insert v into Q
            end if
        done
        u.color = dark_green
    done
end

C++での実装例

以下のコードでは、隣接リストを vector<int> の配列で表現し、キューには queue<int> を使用しています。また、グラフが非連結の場合にも対応できるよう、すべての頂点を始点候補としてBFSを呼び出しています。

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
vector<string> colour;
vector<int> dist;
vector<int> par;

void addEdge(vector <int> g[], int u, int v) { // グラフに辺を追加
    g[u].push_back(v);
    g[v].push_back(u);
}

void BFS(vector <int> g[], int s) {
    queue<int> q;
    q.push(s); // 始点を挿入
    dist[s] = 0;
    colour[s] = "gray";
    while (!q.empty()) {
        int u = q.front(); // キューの先頭要素を取り出して削除
        q.pop();
        cout << u << " ";
        for (auto i = g[u].begin(); i != g[u].end(); i++) {
            if (colour[*i] == "white") { // 白は未訪問の頂点
                colour[*i] = "gray";     // グレーは訪問済みだが未完了
                dist[*i] = dist[u] + 1;
                par[*i] = u;
                q.push(*i);
            }
        }
        colour[u] = "black"; // 黒は処理完了の頂点
    }
}

void BFSAlgo(vector <int> g[], int n) {
    colour.assign(n, "white"); // すべて未訪問として初期化
    dist.assign(n, 0);
    par.assign(n, -1);
    for (int i = 0; i < n; i++)
        if (colour[i] == "white")
            BFS(g, i);
}

int main() {
    int n = 7;
    vector <int> g[n];
    addEdge(g, 0, 1);
    addEdge(g, 0, 2);
    addEdge(g, 1, 3);
    addEdge(g, 1, 4);
    addEdge(g, 2, 5);
    addEdge(g, 2, 6);
    BFSAlgo(g, n);
}

実行結果

このプログラムを実行すると、頂点0を始点として幅優先の順序で各頂点が訪問されます。

0 1 2 3 4 5 6

ポイントのまとめ

BFSはキュー（FIFO）の性質により、始点から近い頂点から順に探索するため、無重みグラフにおける最短経路距離を求めることができます。計算量は頂点数をV、辺数をEとすると O(V + E) です。色の管理によって同じ頂点を二度キューに入れないようにしている点が、このアルゴリズムの効率性の鍵となっています。