タージャンのアルゴリズムで有向グラフの強連結成分(SCC)を求める方法

タージャンのアルゴリズムとは

タージャン(Tarjan)のアルゴリズムは、有向グラフの強連結成分(Strongly Connected Components: SCC)を効率的に求めるためのアルゴリズムです。最大の特徴は、深さ優先探索(DFS)をたった1回実行するだけで、すべての強連結成分を見つけられる点にあります。

DFSによる探索を行うと、グラフから「DFS木」を構成できます。このDFS木をもとに強連結成分が判明します。ある部分木の根が検出された時点で、その部分木全体を出力することができ、この部分木こそが1つの強連結成分となるのです。

アルゴリズムの鍵となる値

• disc[u]:頂点uがDFSによって発見された時刻(訪問順)
• low[u]:頂点uから辿れる頂点の中で最も小さい発見時刻
• low[u] == disc[u]が成立した頂点は強連結成分の「根」であり、この時点でスタックから頂点を取り出すとSCCが得られます。

入力と出力

入力:
グラフの隣接行列
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

出力:
強連結成分:
4
3
1 2 0

アルゴリズム

findComponent(u, disc, low, stack, stackItemFlag)

入力:開始ノード、発見時刻、low値。discは各頂点の発見時刻を保持し、lowは部分木に関する情報を保持します。さらに、頂点を格納するスタックと、どのノードがスタック内に存在するかを追跡するフラグ配列が必要です。

出力:強連結成分(SCC)を表示します。

開始
    time := 0    // time の値は次回以降の関数呼び出しでも初期化されない
    disc[u] := time + 1、low[u] := time + 1 と設定
    time := time + 1
    u をスタックにプッシュ
    stackItemFlag[u] := true

    u に隣接するすべての頂点 v について繰り返す
        もし v が未発見ならば
            findComponent(v, disc, low, stack, stackItemFlag) を再帰呼び出し
            low[u] := min(low[u], low[v])
        そうでなく stackItemFlag[v] が真ならば
            low[u] := min(low[u], disc[v])
    繰り返し終了

    poppedItem := 0
    もし low[u] = disc[u] ならば
        スタックの先頭が u になるまで繰り返す
            poppedItem := スタックの先頭要素
            poppedItem を表示
            stackItemFlag[poppedItem] := false
            スタックからポップ
        繰り返し終了

        poppedItem := スタックの先頭要素
        poppedItem を表示
        stackItemFlag[poppedItem] := false
        スタックからポップ
終了

strongConComponent(graph)

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

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

開始
    disc 配列の全要素を「未発見」に初期化
    low の全要素を φ(空)に設定
    どの要素もスタックに格納されていないものとしてマーク

    グラフ内のすべてのノード i について繰り返す
        もし disc[i] が未発見ならば
            findComponent(i, disc, low, stack, stackItemFlag) を呼び出す
繰り返し終了
終了

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 min(int a, int b) {
    return (a<b)?a:b;
}

void findComponent(int u, int disc[], int low[], stack<int>&stk, bool stkItem[]) {
    static int time = 0;
    disc[u] = low[u] = ++time;     // 発見時刻と low 値を同じ値で初期化
    stk.push(u);
    stkItem[u] = true;             // u がスタック内にあることを記録

    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {
            if(disc[v] == -1) {    // v が未訪問の場合
                findComponent(v, disc, low, stk, stkItem);
                low[u] = min(low[u], low[v]);
            } else if(stkItem[v])  // v がスタック内にある場合、u の low 値を更新
                low[u] = min(low[u], disc[v]);
        }
    }

    int poppedItem = 0;
    if(low[u] == disc[u]) {        // u が強連結成分の根である場合
        while(stk.top() != u) {
            poppedItem = stk.top();
            cout << poppedItem << " ";
            stkItem[poppedItem] = false;    // ポップ済みとしてマーク
            stk.pop();
        }
        poppedItem = stk.top();
        cout << poppedItem << endl;
        stkItem[poppedItem] = false;
        stk.pop();
    }
}

void strongConComponent() {
    int disc[NODE], low[NODE];
    bool stkItem[NODE];
    stack<int> stk;

    for(int i = 0; i<NODE; i++) {  // 全要素を初期化
        disc[i] = low[i] = -1;
        stkItem[i] = false;
    }

    for(int i = 0; i<NODE; i++)    // 未訪問のノードから探索を開始
        if(disc[i] == -1)
            findComponent(i, disc, low, stk, stkItem);
}

int main() {
    strongConComponent();
}

実行結果

4
3
1 2 0

計算量

タージャンのアルゴリズムの計算量は O(V + E) です。DFSを一度しか行わないため、グラフを2回走査する必要があるコーサラジュ(Kosaraju)法などと比較しても非常に効率的で、大規模なグラフ処理にも適しています。