有向グラフの連結性(接続性)の判定方法 ― DFS探索による実装解説

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

有向グラフにおける連結性チェックのポイント

無向グラフと異なり、有向グラフの場合はすべてのノードを起点として探索を行う必要があります。これは、あるノードに外向きの辺のみが存在し、内向きの辺がまったくないケースがあるためです。そのようなノードは、他のどのノードを起点にしても到達できません。

本記事では、探索アルゴリズムとして再帰的なDFS(深さ優先探索)を採用します。

入力と出力

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

出力:
The Graph is connected.(グラフは連結である)

アルゴリズム

traverse(u, visited)

入力: 開始ノード u、および訪問済みノードを記録する visited 配列

出力: u から到達可能なすべての頂点を巡回する

Begin
    mark u as visited(u を訪問済みとしてマーク)
    for all vertex v, if it is adjacent with u, do
       if v is not visited, then
          traverse(v, visited)
    done
End

isConnected(graph)

入力: 判定対象のグラフ

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

Begin
    define visited array(visited 配列を定義)
    for all vertices u in the graph, do
       make all nodes unvisited(全ノードを未訪問に初期化)
       traverse(u, visited)
       if any unvisited node is still remaining, then
          return false
    done
    return 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]) {          // u から v への辺が存在する場合
            if(!visited[v])        // 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.

このように、各ノードを順番に起点としてDFSを実行し、毎回すべてのノードに到達できるかを検証することで、有向グラフの連結性を正確に判定できます。計算量は O(V × (V + E)) となり、小規模なグラフであれば十分実用的な手法です。