C++で無向グラフの連結成分を求める方法｜DFSによる強連結・弱連結の判定

無向グラフが「弱連結（weakly connected）」か「強連結（strongly connected）」かを判定するには、DFS（深さ優先探索）を利用できます。この記事では、グラフの連結成分を見つけ出し、その連結状態を判定するC++プログラムを紹介します。

この実装は「コサラジュ（Kosaraju）のアルゴリズム」と呼ばれる手法に基づいています。まず1回目のDFSで各頂点の探索完了順をスタックに記録し、続いてすべての辺の向きを反転させた「転置グラフ」を作成します。その後、スタックから頂点を取り出す順に2回目のDFSを実行することで、強連結成分を効率的に抽出できます。

アルゴリズムで使用する関数

Begin
Function fillOrder()：スタックにすべての頂点を格納する
　　a) 現在のノードを訪問済みとしてマークする
　　b) この頂点に隣接するすべての頂点に対して再帰的に処理する
　　c) 頂点vから到達できるすべての頂点の処理が完了したら、vをスタックに積む
End

Begin
Function DFS()：
　　a) 現在のノードを訪問済みとしてマークする
　　b) この頂点に隣接するすべての頂点に対して再帰的に処理する
End

C++による実装例

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class G {
    int m;
    list<int> *adj;
    // 関数の宣言
    void fillOrder(int n, bool visited[], stack<int> &Stack);
    void DFS(int n, bool visited[]);
public:
    G(int N); // コンストラクタ
    void addEd(int v, int w);
    int print();
    G getTranspose();
};

G::G(int m) {
    this->m = m;
    adj = new list<int>[m];
}

// 深さ優先探索（DFS）
void G::DFS(int n, bool visited[]) {
    visited[n] = true; // 現在のノードを訪問済みとしてマーク
    cout << n << " ";
    list<int>::iterator i;
    // 隣接するすべての頂点に対して再帰的に処理
    for (i = adj[n].begin(); i != adj[n].end(); ++i)
        if (!visited[*i])
            DFS(*i, visited);
}

// すべての辺の向きを反転した転置グラフを生成
G G::getTranspose() {
    G g(m);
    for (int n = 0; n < m; n++) {
        list<int>::iterator i;
        for (i = adj[n].begin(); i != adj[n].end(); ++i) {
            g.adj[*i].push_back(n);
        }
    }
    return g;
}

// 辺の追加（w を v の隣接リストに登録）
void G::addEd(int v, int w) {
    adj[v].push_back(w);
}

// 探索が完了した順にスタックへ頂点を積む
void G::fillOrder(int v, bool visited[], stack<int> &Stack) {
    visited[v] = true; // 現在のノードを訪問済みとしてマーク
    list<int>::iterator i;
    // 隣接するすべての頂点に対して再帰的に処理
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            fillOrder(*i, visited, Stack);
    // vから到達できる頂点をすべて処理し終えたらスタックに積む
    Stack.push(v);
}

// 強連結成分を求めて表示し、成分の個数を返す
int G::print() {
    stack<int> Stack;
    bool *visited = new bool[m];
    for (int i = 0; i < m; i++)
        visited[i] = false;

    // すべての頂点に対して fillOrder を実行
    for (int i = 0; i < m; i++)
        if (visited[i] == false)
            fillOrder(i, visited, Stack);

    G graph = getTranspose(); // 転置グラフを作成

    for (int i = 0; i < m; i++) // 全頂点を未訪問に戻す
        visited[i] = false;

    int count = 0;
    // スタックで定義された順序ですべての頂点を処理
    while (Stack.empty() == false) {
        int v = Stack.top();
        Stack.pop(); // 頂点をスタックから取り出す
        if (visited[v] == false) {
            graph.DFS(v, visited); // 新しい強連結成分を1つ発見
            cout << endl;
            count++;               // 成分の個数をカウント
        }
    }
    return count;
}

int main() {
    G g(5);
    g.addEd(2, 1);
    g.addEd(3, 2);
    g.addEd(1, 0);
    g.addEd(0, 3);
    g.addEd(3, 1);

    cout << "与えられたグラフの強連結成分は以下の通りです\n";
    if (g.print() > 1) {
        cout << "グラフは弱連結です。";
    } else {
        cout << "グラフは強連結です。";
    }
    return 0;
}

実行結果

与えられたグラフの強連結成分は以下の通りです
4
0 1 2 3
グラフは弱連結です。

プログラムのポイント

• 計算量： DFSを2回実行するだけのため、頂点数V・辺数Eのグラフに対して時間計算量はO(V+E)と非常に効率的です。
• 転置グラフの役割： getTranspose() は辺の向きをすべて反転したグラフを生成します。同じ強連結成分内の頂点同士は互いに到達可能であるため、転置しても成分の構成は変わりません。
• 連結性の判定： print() が返す強連結成分の数が1つであれば強連結、2つ以上あれば弱連結（または非連結）と判定できます。

この例では、頂点「4」が単独の成分、「0・1・2・3」がもう一つの成分として検出されています。グラフ全体が複数の連結成分に分かれているため、「弱連結」という結果が表示されます。