BFS（幅優先探索）で無向グラフの連結性を判定するC++プログラム

グラフの連結性とは

グラフが連結（接続）されているかどうかを調べるには、何らかのグラフ探索アルゴリズムを使って、すべてのノードを訪問できるかどうかを確認します。探索を完了した時点で未訪問のノードが1つでも残っていれば、そのグラフは連結していないことになります。

無向グラフの場合は、任意の1つのノードを選び、そこから探索を開始します。本記事では、探索アルゴリズムとして幅優先探索（BFS：Breadth-First Search）を採用しています。

入力と出力の例

入力 − グラフの隣接行列

出力 − 「グラフは連結しています。」

アルゴリズム

traverse(s, visited)

入力 − 開始ノード s、および訪問済みノードを記録するための visited 配列。

出力 − 開始ノードから到達可能なすべての頂点を探索します。

開始
   s を訪問済みとしてマークする
   s をキュー Q に挿入する
   キュー Q が空になるまで、以下を繰り返す
      u ← キューから取り出したノード
      グラフ内の各ノード v について繰り返す
         u と v が接続されている場合、
            v が未訪問であれば、
               v を訪問済みとしてマークする
               v をキュー Q に挿入する
      繰り返しここまで
   繰り返しここまで
終了

isConnected(graph)

入力 − 判定対象のグラフ。

出力 − グラフが連結していれば true、そうでなければ false。

開始
   visited 配列を定義する
   グラフ内のすべての頂点 u について繰り返す
      すべてのノードを未訪問状態に戻す
      traverse(u, visited) を呼び出す
      未訪問のノードがまだ残っている場合、
         false を返す
   繰り返しここまで
   true を返す
終了

C++による実装例

以下は、隣接行列で表現された5頂点の無向グラフに対して、BFSを用いて連結性を判定するC++プログラムです。

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

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

// 幅優先探索（BFS）で到達可能なノードをすべて訪問する
void traverse(int s, bool visited[]) {
    visited[s] = true; // ノードsを訪問済みとしてマーク
    queue<int> que;
    que.push(s); // sをキューに挿入
    while(!que.empty()) {
        int u = que.front(); // キューの先頭要素を取り出す
        que.pop();
        for(int i = 0; i < NODE; i++) {
            if(graph[i][u]) {
                // ノードiが未訪問の場合
                if(!visited[i]) {
                    visited[i] = true;
                    que.push(i);
                }
            }
        }
    }
}

// グラフ全体が連結しているかどうかを判定する
bool isConnected() {
    bool *vis = new bool[NODE];
    // 各頂点uを起点として、全ノードが訪問可能かどうかを確認する
    for(int u = 0; u < NODE; u++) {
        for(int i = 0; i < NODE; i++)
            vis[i] = false; // すべてのノードを未訪問として初期化
        traverse(u, vis);
        for(int i = 0; i < NODE; i++) {
            if(!vis[i]) // 探索で訪問できなかったノードがあれば、グラフは非連結
                return false;
        }
    }
    return true;
}

int main() {
    if(isConnected())
        cout << "The Graph is connected.";
    else
        cout << "The Graph is not connected.";
}

なお、隣接行列を用いたこの実装の計算量は、頂点数を V とすると O(V²) となります。頂点数が多いグラフを扱う場合は、隣接リスト表現と組み合わせることで効率化を図ることができます。

実行結果

The Graph is connected.