C++で有向グラフが連結しているかどうかを判定する方法

グラフの連結性（接続性）を確認するには、何らかの探索アルゴリズムを使ってすべてのノードを巡回してみます。探索が完了した時点で、まだ訪問されていないノードが1つでも残っていれば、そのグラフは連結していないと判断できます。

有向グラフの場合は、すべてのノードから順に探索を開始して連結性をチェックします。これは、あるエッジが外向きの辺しか持たず内向きの辺を持たない場合、そのノードには他のどの開始ノードからも到達できない可能性があるためです。

本記事では、この探索アルゴリズムとして再帰的なDFS（深さ優先探索）を使用します。

入力と出力

入力 − グラフの隣接行列

出力 − グラフは連結しています。

アルゴリズム

traverse(u, visited)

入力： 開始ノード u と、訪問済みノードを記録する visited 配列
出力： 到達可能なすべての頂点を巡回する

traverse(u, visited)
Begin
    u を訪問済みとしてマークする
    u に隣接するすべての頂点 v について、以下を実行する
        v が未訪問であれば
            traverse(v, visited) を呼び出す
    完了
End

isConnected(graph)

入力： グラフ
出力： グラフが連結していれば true、そうでなければ false

isConnected(graph)
Begin
    visited 配列を定義する
    グラフ内のすべての頂点 u について、以下を実行する
        すべてのノードを未訪問状態に初期化する
        traverse(u, visited) を実行する
        未訪問のノードがまだ残っている場合は
            false を返す
    完了
    true を返す
End

C++による実装例

#include<iostream>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {{0, 1, 0, 0, 0},
   {0, 0, 1, 0, 0},
   {0, 0, 0, 1, 1},
   {1, 0, 0, 0, 0},
   {0, 1, 0, 0, 0}
};
void traverse(int u, bool visited[]){
   visited[u] = true; // u を訪問済みとしてマーク
   for(int v = 0; v<NODE; v++){
      if(graph[u][v]){
         if(!visited[v])
         traverse(v, visited);
      }
   }
}
bool isConnected(){
   bool *vis = new bool[NODE];
   // すべての頂点 u を開始点として、全ノードが訪問できるか確認する
   for(int u = 0; u < NODE; u++){
      for(int i = 0; i<NODE; i++)
      vis[i] = false; // すべてのノードを未訪問として初期化
      traverse(u, vis);
      for(int i = 0; i<NODE; i++){
         if(!vis[i]) // 探索で訪問されなかったノードがあれば、グラフは非連結
         return false;
      }
   }
   return true;
}
int main(){
   if(isConnected())
   cout << "The Graph is connected.";
   else
   cout << "The Graph is not connected.";
}

実行結果

The Graph is connected.

解説

このプログラムでは、まず traverse 関数が再帰的なDFSを実装しています。開始ノードを訪問済みにマークし、隣接する未訪問ノードに対して再帰的に自分自身を呼び出すことで、到達可能なすべての頂点を巡回します。

isConnected 関数では、各頂点を開始点として探索を行い、毎回 visited 配列をリセットします。5つの頂点それぞれから探索しても全ノードに到達できれば、その有向グラフは強連結であると判定できます。計算量は O(V × (V + E)) となり、V は頂点数、E はエッジ数です。