有向グラフの強連結成分を求めるC++プログラム（コサラジュのアルゴリズム）

強連結成分（SCC）とは

有向グラフにおいて、任意の2つの頂点 u と v の間で「u から v への経路」と「v から u への経路」がどちらも存在するとき、そのグラフは強連結（strongly connected）であるといいます。グラフ全体が強連結でない場合でも、互いに到達し合える頂点同士でグループ化すると、グラフを複数の強連結成分（SCC: Strongly Connected Components）に分解できます。

強連結成分の検出には、DFS（深さ優先探索）を2回実行するコサラジュ（Kosaraju）のアルゴリズムが広く知られています。検出された強連結成分が1つだけであればグラフは強連結、2つ以上であれば弱連結であると判定できます。

アルゴリズムの流れ

コサラジュのアルゴリズムは、次の3ステップで構成されます。

1. fillOrder： グラフに対してDFSを実行し、探索が完了した頂点から順にスタックへ積みます。
2. getTranspose： すべての辺の向きを反転させた転置グラフ（逆グラフ）を作成します。
3. print： スタックから頂点を1つずつ取り出し、未訪問であれば転置グラフ上でDFSを実行します。このとき到達できる頂点の集合が、1つの強連結成分となります。

使用する関数の擬似コード

開始
関数 fillOrder()：すべての頂点でスタックを埋める
    a) 現在のノードを訪問済みとしてマークする
    b) この頂点に隣接するすべての頂点に対して再帰的に呼び出す
    c) v から到達可能なすべての頂点の処理が完了したら、v をスタックにプッシュする
終了

開始
関数 DFS()：
    a) 現在のノードを訪問済みとしてマークし、出力する
    b) この頂点に隣接するすべての頂点に対して再帰的に呼び出す
終了

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;
}
void G::addEd(int v, int w) {
    adj[v].push_back(w); // v の隣接リストに 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
このグラフは弱連結です。

結果の解説

この例では、5つの頂点（0〜4）を持つグラフを扱っています。頂点0、1、2、3は互いに到達し合えるため1つの強連結成分を構成し、一方、頂点4はどの辺にも接続されていないため単独で1つの強連結成分になります。その結果、強連結成分の数は2となり、プログラムは「このグラフは弱連結です」と出力します。

計算量は、DFSを2回実行するだけなので、頂点数を V、辺数を E とすると O(V + E) となり、大規模なグラフに対しても効率的に動作します。