有向グラフが「強連結」か「弱連結」かを判定するC++プログラム（DFSを活用）

有向グラフが強連結（strongly connected）であるとは、グラフ内の任意の2頂点について、互いに到達可能な経路が存在することを意味します。一方、弱連結（weakly connected）とは、すべての辺の向きを無視した場合にのみ全体がつながっている状態を指します。

これらの性質は、DFS（深さ優先探索）を用いて判定できます。具体的には、コサラジュのアルゴリズム（Kosaraju's algorithm）によって強連結成分（SCC）を求め、成分が1つだけなら強連結、2つ以上に分かれるなら弱連結と判断します。以下に、そのC++プログラムを紹介します。

使用する関数

本プログラムでは、次の2つの再帰関数を中心に処理を構成します。

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];
}

// 深さ優先探索：現在のノードを訪問済みにして出力し、隣接頂点へ再帰
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;
}

// 辺の追加：vのリストにwを加える
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);
    Stack.push(v);
}

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

    // すべての頂点をスタックへ格納
    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);
            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
グラフは弱連結です。

プログラムのポイント

• getTranspose()：すべての辺の向きを反転させた転置グラフを生成します。
• fillOrder()：最初のDFSで各頂点の探索完了順序をスタックに記録します。
• print()：スタックから頂点を取り出しながら転置グラフ上でDFSを実行し、強連結成分ごとに出力します。戻り値は成分の個数です。
• main()：成分数が1より大きければ弱連結、ちょうど1つなら強連結と判定して表示します。

サンプルコードでは、頂点0〜4の5頂点からなるグラフに、辺 (2,1)、(3,2)、(1,0)、(0,3)、(3,1) を追加しています。この例では {0, 1, 2, 3} と {4} の2つの強連結成分に分かれるため、プログラムは「グラフは弱連結です。」と出力します。もしグラフ全体が単一の強連結成分で構成されていれば、出力は「グラフは強連結です。」となります。