強連結グラフとは？強連結成分（SCC）を求めるアルゴリズムをC++で解説

有向グラフにおいて、同じ成分内の任意の2つの頂点の間に、双方向への経路が存在するとき、そのグラフは「強連結（strongly connected）」であると言われます。このような頂点の集合を「強連結成分（Strongly Connected Component：SCC）」と呼びます。

強連結成分を求める考え方

この問題を解くためには、コラサジュのアルゴリズム（Kosaraju's Algorithm）と呼ばれる手法がよく用いられます。手順は以下の通りです。

1. まずDFS（深さ優先探索）を実行し、各頂点の「完了時刻（finish time）」を記録します。
2. 次に、元のグラフのすべての辺の向きを反転させた「転置グラフ」を作成します。
3. 完了時刻の降順になるようトポロジカルソートの順序で頂点を取り出しながら、転置グラフ上で再度DFSを行うと、それぞれの探索木が強連結成分となります。

入力と出力

Input:
グラフの隣接行列。
0 0 1 1 0
1 0 0 0 0
0 1 0 0 0
0 0 0 0 1
0 0 0 0 0

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

アルゴリズム

traverse(graph, start, visited)

入力： 探索対象のグラフ、開始頂点、訪問済みノードのフラグ配列。

出力： DFSの技法で各ノードを順に訪問し、ノードを表示します。

Begin
    mark start as visited
    for all vertices v connected with start, do
        if v is not visited, then
            traverse(graph, v, visited)
    done
End

topoSort(u, visited, stack)

入力： 開始ノード、訪問済み頂点のフラグ、スタック。

出力： グラフをソートしながらスタックを埋めていきます。再帰呼び出しが完了した後に頂点をプッシュすることで、完了時刻の降順が得られます。

Begin
    mark u as visited
    for all node v, connected with u, do
        if v is not visited, then
            topoSort(v, visited, stack)
    done
    push u into the stack
End

getStrongConComponents(graph)

入力： 与えられたグラフ。

出力： すべての強連結成分。

Begin
    initially all nodes are unvisited
    for all vertex i in the graph, do
        if i is not visited, then
            topoSort(i, vis, stack)
    done

    make all nodes unvisited again
    transGraph := transpose of given graph

    while stack is not empty, do
        pop node from stack and take into v
        if v is not visited, then
            traverse(transGraph, v, visited)
    done
End

C++による実装例

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

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

int transGraph[NODE][NODE];

void transpose() {     // グラフを転置してtransGraphに格納する
    for(int i = 0; i<NODE; i++)
        for(int j = 0; j<NODE; j++)
            transGraph[i][j] = graph[j][i];
}

void traverse(int g[NODE][NODE], int u, bool visited[]) {
    visited[u] = true;     // 頂点uを訪問済みとしてマーク
    cout << u << " ";

    for(int v = 0; v<NODE; v++) {
        if(g[u][v]) {
            if(!visited[v])
                traverse(g, v, visited);
        }
    }
}

void topoSort(int u, bool visited[], stack<int>&stk) {
    visited[u] = true;     // 頂点uを訪問済みとして設定

    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {     // uに隣接するすべての頂点vに対して
            if(!visited[v])
                topoSort(v, visited, stk);
        }
    }

    stk.push(u);     // 開始頂点をスタックにプッシュ
}

void getStrongConComponents() {
    stack<int> stk;
    bool vis[NODE];

    for(int i = 0; i<NODE; i++)
        vis[i] = false;     // 初期状態では全ノード未訪問

    for(int i = 0; i<NODE; i++)
        if(!vis[i])     // ノードが未訪問の場合
            topoSort(i, vis, stk);

    for(int i = 0; i<NODE; i++)
        vis[i] = false;     // 探索のために全ノードを未訪問に戻す
    transpose();     // 辺の向きを反転したグラフを作成

    while(!stk.empty()) {     // スタックに要素がある間、トポロジカル順に処理
        int v = stk.top(); stk.pop();
        if(!vis[v]) {
            traverse(transGraph, v, vis);
            cout << endl;
        }
    }
}

int main() {
    cout << "Following are strongly connected components in given graph: "<<endl;
    getStrongConComponents();
}

実行結果

Following are strongly connected components in given graph:
0 1 2
3
4

この実行結果から、頂点0・1・2が互いに到達可能な一つの強連結成分を構成し、頂点3と4はそれぞれ単独の強連結成分となっていることが分かります。このアルゴリズムの計算量は、DFSを2回行うためO(V + E)です（Vは頂点数、Eは辺数）。