C++でグラフが強連結かどうかを判定する方法 ― DFSを用いたコサラジュのアルゴリズム（その1）

グラフが強連結（strongly connected）であるかどうかを、コサラジュ（Kosaraju）のアルゴリズムと深さ優先探索（DFS）を使って判定する方法を解説します。

強連結グラフとは？

グラフ内の任意の2つの頂点の間に、双方向へのパスが存在するとき、そのグラフは「強連結」であるといいます。なお、無向グラフは辺が双方向に移動できるため、連結であれば自動的に強連結となります。

一方、有向グラフの場合は注意が必要です。連結ではあっても強連結ではないグラフも存在します。例えば、ある頂点から別の頂点へ一方通行でしか到達できない場合、そのグラフは連結ですが強連結ではありません。

コサラジュのアルゴリズムによる判定手順

ここでは、以下の手順に従ってグラフが強連結かどうかをチェックします。

1. 初期化： すべてのノードを「未訪問」としてマークします。
2. 順方向のDFS： 任意の頂点 u からDFS（深さ優先探索）を開始します。すべてのノードを訪問できなかった場合は false を返します。
3. 辺の反転： グラフのすべての辺の向きを逆にします。
4. 再初期化： すべての頂点を再び「未訪問」に設定します。
5. 逆方向のDFS： 同じ頂点 u から再度DFSを実行します。すべてのノードを訪問できれば true、できなければ false を返します。

なぜこの方法で判定できるのか？

元のグラフですべての頂点に到達でき、かつ辺を反転させたグラフでもすべての頂点に到達できるということは、どの頂点からどの頂点へも到達可能であることを意味します。つまり、そのグラフは強連結であると判定できるのです。

C++による実装例

以下は、隣接リスト形式のグラフクラスを用いて上記アルゴリズムを実装したC++のコードです。

#include <iostream>
#include <list>
#include <stack>
using namespace std;
class Graph {
    int V;
    list<int> *adj;
    void dfs(int v, bool visited[]);
    public:
    Graph(int V) {
        this->V = V;
        adj = new list<int>[V];
    }
    ~Graph() {
        delete [] adj;
    }
    void addEdge(int v, int w);
    bool isStronglyConnected();
    Graph reverseArc();
};
void Graph::dfs(int v, bool visited[]) {
    visited[v] = true;
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
    if (!visited[*i])
        dfs(*i, visited);
}
Graph Graph::reverseArc() {
    Graph graph(V);
    for (int v = 0; v < V; v++) {
        list<int>::iterator i;
        for(i = adj[v].begin(); i != adj[v].end(); ++i)
            graph.adj[*i].push_back(v);
    }
    return graph;
}
void Graph::addEdge(int u, int v) {
    adj[u].push_back(v);
}
bool Graph::isStronglyConnected() {
    bool visited[V];
    for (int i = 0; i < V; i++)
        visited[i] = false;
    dfs(0, visited);
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            return false;
    Graph graph = reverseArc();
    for(int i = 0; i < V; i++)
        visited[i] = false;
    graph.dfs(0, visited);
    for (int i = 0; i < V; i++)
        if (visited[i] == false)
            return false;
    return true;
}
int main() {
    Graph graph(5);
    graph.addEdge(0, 1);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 0);
    graph.addEdge(2, 4);
    graph.addEdge(4, 2);
    graph.isStronglyConnected()? cout << "This is strongly connected" : cout << "This is not strongly connected";
}

実行結果

This is strongly connected

このサンプルコードでは、5つの頂点を持つ有向グラフを作成しています。頂点0→1→2→3→0が閉路を形成し、さらに頂点2と4の間にも双方向の辺があるため、このグラフは強連結であると正しく判定されました。

計算量について

このアルゴリズムでは、DFSを2回実行し、辺の反転を1回行います。いずれの処理も頂点数 V と辺数 E に対して線形時間で動作するため、全体の計算量は O(V + E) となり、非常に効率的です。