DFS(深さ優先探索)を使って無向グラフの連結性を判定するC++プログラム

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

無向グラフの場合は、任意の1つのノードを選び、そこから探索を開始します。本記事では、探索アルゴリズムとして再帰的なDFS(深さ優先探索)を使用します。

入力と出力

入力 − グラフの隣接行列

出力 − 「The Graph is connected.」(グラフは連結している)

アルゴリズム

traverse(u, visited)

入力 − 探索の開始ノード u と、訪問済みノードを記録するための visited 配列。

出力 − u から到達可能なすべての頂点を探索します。

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

isConnected(graph)

入力 − 判定対象のグラフ。

出力 − グラフが連結であれば true、そうでなければ false。

開始
   visited 配列を定義する
   グラフ内のすべての頂点 u について:
      すべてのノードを未訪問状態に初期化する
      traverse(u, visited) を実行する
      未訪問のノードがまだ残っている場合は
         false を返す
   繰り返し終了
   true を返す
終了

コードの解説

• traverse関数:指定された頂点 u を訪問済みにした後、隣接行列を走査し、u に隣接する未訪問の頂点に対して自分自身を再帰的に呼び出します。これにより、u から到達できるすべての頂点が訪問されます。
• isConnected関数:各頂点を起点としてDFSを実行し、そのたびに visited 配列を初期化します。探索後に未訪問の頂点が1つでも残っていれば、そのグラフは非連結であるため false を返します。

サンプルコード(C++)

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

int graph[NODE][NODE] = {{0, 1, 1, 0, 0},
                         {1, 0, 1, 1, 0},
                         {1, 1, 0, 1, 1},
                         {0, 1, 1, 0, 1},
                         {0, 0, 1, 1, 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.

補足:計算量について

隣接行列を用いた実装では、1回のDFSに O(V²) の時間がかかるため、すべての頂点を起点として検証する本プログラム全体の計算量は O(V³) となります。なお、無向グラフの場合、理論上は任意の1頂点からDFSを1回実行し、すべての頂点が訪問されれば連結と判定できるため、計算量は O(V²) に抑えられます。本プログラムのように全頂点を起点に検証する方式はやや冗長ですが、判定の確実性を高めるという意味で有効です。また、隣接リストを用いればDFS自体を O(V + E) で実装でき、大規模な疎グラフでは大幅な高速化が期待できます。