C++で非連結グラフに対するBFS（幅優先探索）を実装する方法

非連結グラフとは

非連結グラフ（disconnected graph）とは、グラフ内の1つ以上の頂点が他の頂点と辺でつながっておらず、どこかの頂点から出発しても到達できない頂点が存在するグラフのことです。このようなグラフは、複数の「連結成分（connected component）」に分かれている状態と捉えることができます。

通常のBFSでは不十分な理由

単純な幅優先探索（BFS: Breadth First Search）が正しく機能するのは、グラフが連結している場合、すなわちグラフ内のすべての頂点がある1つの頂点から到達できる場合だけです。非連結グラフでは、開始頂点から到達できない頂点が必ず存在するため、1回のBFSを実行しただけではグラフ全体を探索しきれません。

解決策：全頂点を起点としてBFSを繰り返す

この問題を解決するには、すべての頂点を順番にチェックし、まだ訪問していない頂点が見つかるたびに、その頂点を新たな起点としてBFSを実行するようにします。訪問済みかどうかを記録する配列（visited）を用意しておくのがポイントです。こうすることで、グラフがいくつの連結成分に分かれていても、すべての頂点を確実に訪問できます。

アルゴリズムの流れ

1. すべての頂点を「未訪問」に初期化したvisited配列を用意する。
2. 頂点0からV-1まで順番にループする。
3. 未訪問の頂点が見つかったら、その頂点を起点にBFSを実行する。
4. BFS内では、キューを使って頂点を取り出しながら、隣接する未訪問の頂点をすべてキューに追加していく。

C++での実装例

以下は、隣接リスト形式のグラフに対して、非連結グラフにも対応したBFSを実装したC++のサンプルコードです。

#include <bits/stdc++.h>
using namespace std;

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

// 頂点uを起点とする幅優先探索（BFS）
void bfs(int u, vector<int> adj[], vector<bool> &visited) {
    list<int> q;
    visited[u] = true;
    q.push_back(u);

    while (!q.empty()) {
        u = q.front();
        cout << u << " ";
        q.pop_front();

        for (int i = 0; i != adj[u].size(); ++i) {
            if (!visited[adj[u][i]]) {
                visited[adj[u][i]] = true;
                q.push_back(adj[u][i]);
            }
        }
    }
}

// 非連結グラフ全体に対するBFS
void bfsDisconnected(vector<int> adj[], int V) {
    vector<bool> visited(V, false);
    for (int u = 0; u < V; u++)
        if (!visited[u])
            bfs(u, adj, visited);
}

int main() {
    int V = 5;
    vector<int> adj[V];

    addEdge(adj, 0, 4);
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 1, 3);
    addEdge(adj, 1, 4);
    addEdge(adj, 2, 3);
    addEdge(adj, 3, 4);

    bfsDisconnected(adj, V);
    return 0;
}

実行結果

0 4 1 2 3

この例では頂点0から探索が開始され、頂点が「0 → 4 → 1 → 2 → 3」の順に訪問されます。仮にグラフが非連結で、頂点0から到達できない頂点があったとしても、bfsDisconnected関数がすべての頂点をチェックするため、その頂点も必ず探索されます。

計算量

このアルゴリズムの時間計算量は O(V + E) です（Vは頂点数、Eは辺数）。各頂点と各辺は高々1回ずつ処理されるため、非連結グラフでも効率よく全頂点を探索できます。空間計算量はvisited配列とキューの分が必要となり、O(V)です。

まとめ

非連結グラフに対するBFSでは、「訪問済みフラグを管理しながら、未訪問の頂点がなくなるまでBFSを繰り返す」ことが重要です。このテクニックは、連結成分の個数を数えたり、グラフが連結しているかどうかを判定したりする際にも応用できます。