C++で有向グラフの強連結成分を検出するプログラムの作成方法

有向グラフにおいて、ある成分内の任意の頂点ペア同士の間に経路が存在するとき、その成分は「強く接続されている（強連結）」といいます。このような成分のことを強連結成分（SCC: Strongly Connected Components）と呼びます。

この問題を解くには、まずDFS（深さ優先探索）を使って各頂点の完了時刻（finish time）を求めます。次にグラフを転置し、完了時刻をもとに頂点を降順に並べる（トポロジカルソート）ことで、強連結成分を一つずつ取り出します。これは有名なKosarajuのアルゴリズムに基づいた手法です。

入力： グラフの隣接行列

出力： 与えられたグラフに含まれる強連結成分は以下の通りです −

0 1 2
3
4

アルゴリズム

traverse(graph, start, visited)

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

出力： DFSの手法ですべてのノードを巡回し、ノードを表示します。

開始
　　start を訪問済みとしてマーク
　　start に接続するすべての頂点 v について繰り返す
　　　　v が未訪問であれば
　　　　　　traverse(graph, v, visited) を呼び出す
　　繰り返し終了
終了

topoSort(u, visited, stack)

入力 − 開始ノード、訪問済みフラグ、スタック

出力 − グラフをソートしながらスタックを埋めていきます。

開始
　　u を訪問済みとしてマーク
　　u に接続するすべてのノード v について繰り返す
　　　　v が未訪問であれば
　　　　　　topoSort(v, visited, stack) を呼び出す
　　繰り返し終了
　　u をスタックにプッシュ
終了

getStrongConComponents(graph)

入力 − 与えられたグラフ

出力 − すべての強連結成分

開始
　　最初はすべてのノードを未訪問とする
　　グラフ内のすべての頂点 i について繰り返す
　　　　i が未訪問であれば
　　　　　　topoSort(i, vis, stack) を呼び出す
　　繰り返し終了
　　すべてのノードを再び未訪問に戻す
　　transGraph := 与えられたグラフの転置
　　スタックが空になるまで繰り返す
　　　　スタックからノードをポップして v に代入
　　　　v が未訪問であれば
　　　　　　traverse(transGraph, v, visited) を呼び出す
　　繰り返し終了
終了

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 << "与えられたグラフの強連結成分は以下の通りです: "<<endl;
   getStrongConComponents();
}

実行結果

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

計算量について

このアルゴリズムでは、DFSを元のグラフと転置グラフのそれぞれに対して1回ずつ実行します。したがって、頂点数を V、辺数を E とすると、全体の計算量は O(V + E) となり、非常に効率的な手法です。頂点数5のこの例では、頂点 {0, 1, 2} が互いに行き来可能な一つの強連結成分を構成し、頂点 3 と 4 はそれぞれ単独の成分として検出されています。