BFSを用いて有向グラフの連結性を判定するC++プログラム

グラフの連結性を調べるには、何らかの探索アルゴリズムを使ってすべてのノードを辿ってみます。探索が完了した時点で、まだ訪問していないノードが1つでも残っていれば、そのグラフは連結していないと判断できます。

有向グラフの場合は、すべてのノードを起点として探索を実行する必要があります。あるノードへの辺が外向きのみで内向きの辺を持たない場合、そのノードは他のどの起点から探索しても未訪問のままになる可能性があるためです。

この記事では、探索アルゴリズムとしてBFS（幅優先探索）を使用します。

入力 − グラフの隣接行列

出力 − The Graph is connected.（グラフは連結している）

アルゴリズム

traverse(s, visited)

入力: 開始ノードsと、訪問済みノードを記録するためのvisited配列。
出力: 開始ノードから到達可能なすべての頂点を探索します。

Begin
    s を訪問済みとしてマークする
    s をキューQに挿入する
    Qが空でない間、以下を繰り返す
        u = キューから取り出したノード
        グラフ内の各ノードvについて
            uとvが接続している場合
                vが未訪問ならば
                    vを訪問済みとしてマークする
                vをキューQに挿入する
done
done
End

isConnected(graph)

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

Begin
    visited配列を定義する
    グラフ内のすべての頂点uについて
        すべてのノードを未訪問に初期化する
        traverse(u, visited) を実行する
        未訪問のノードがまだ残っている場合は
            falseを返す
done
    trueを返す
End

C++による実装例

#include<iostream>
#include<queue>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
    {0, 1, 0, 0, 0},
    {0, 0, 1, 0, 0},
    {0, 0, 0, 1, 1},
    {1, 0, 0, 0, 0},
    {0, 1, 0, 0, 0}};

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.";
}

実行結果

The Graph is connected.

解説のポイント

このプログラムでは、各頂点を順番に起点としてBFSを実行し、毎回すべてのノードが訪問できたかどうかを確認しています。すべての起点から全ノードに到達できるということは、この有向グラフが強連結であることを意味します。

計算量について見てみましょう。隣接行列を用いた場合、1回のBFSでO(V²)の時間がかかり、これをV個の頂点それぞれについて実行するため、全体の計算量はO(V³)となります。頂点数が多いグラフでは、隣接リストを使用することで効率を大幅に改善できます。

なお、無向グラフの場合は任意の1点からの探索だけで連結性を判定できますが、有向グラフでは辺に向きがあるため、このように全頂点を起点とした探索が必要になる点に注意してください。