グラフが木（ツリー）であるかどうかを判定するアルゴリズム

木であるかの判定基準

この問題では、1つの無向グラフが与えられ、そのグラフが木（ツリー）であるかどうかを判定します。判定は木の性質を確認するだけで簡単に行えます。木には閉路（サイクル）が含まれないため、グラフ内に閉路がひとつでも存在すれば、そのグラフは木ではありません。

別のアプローチもあります。グラフが連結であり、かつ辺の本数が V−1 であれば、そのグラフは木であると判定できます。ここで V はグラフの頂点数です。これは「連結なグラフが V−1 本の辺を持つならば、必ず閉路を持たない」というグラフ理論の性質に基づいています。

入力と出力

入力：
隣接行列
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
0 0 0 0 1
1 1 1 1 0

出力：
このグラフは木です

アルゴリズム

isCycle(u, visited, parent)

入力：開始頂点 u、訪問状態を記録する visited リスト、親頂点。

出力：グラフ内に閉路が存在する場合は true。

開始
   u を訪問済みとしてマークする
   u に隣接するすべての頂点 v について繰り返す
      もし v が未訪問であれば
         isCycle(v, visited, u) が true であれば
            true を返す
      そうでなく v が親頂点 parent と異なる場合
         true を返す（閉路を検出）
   繰り返し終了
   false を返す
終了

isTree(graph)

入力：無向グラフ。

出力：グラフが木である場合は true。

開始
   訪問状態を記録する配列 visited を用意する
   最初にすべてのノードを未訪問として初期化する
   isCycle(0, visited, φ) が true であれば false を返す
   ※開始頂点の親は null（存在しない）
   グラフが連結でなければ false を返す
   それ以外の場合は true を返す
終了

このアルゴリズムでは、DFS（深さ優先探索）を利用して閉路の有無を調べます。探索中に「訪問済みだが親ではない」頂点へ再びたどり着いた場合、そこに閉路が存在すると判断できます。さらに、探索終了後に未訪問の頂点が残っていた場合は、グラフが連結していないことを意味します。閉路が存在せず、かつグラフ全体が連結していれば、そのグラフは木であると結論付けられます。

C++による実装例

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

int graph[NODE][NODE] = {
    {0, 1, 1, 1, 0},
    {1, 0, 1, 0, 0},
    {1, 1, 0, 0, 0},
    {1, 0, 0, 0, 1},
    {0, 0, 0, 1, 0}
};

bool isCycle(int u, bool visited[], int parent) {
    visited[u] = true;    //u を訪問済みとしてマーク
    for(int v = 0; v<NODE; v++) {
        if(graph[u][v]) {
            if(!visited[v]) {    //隣接ノード v が未訪問の場合
                if(isCycle(v, visited, u)) {
                    return true;
                }
            } else if(v != parent) {    //隣接頂点が訪問済みだが親ではない場合
                return true;    //閉路が存在する
            }
        }
    }
    return false;
}

bool isTree() {
    bool *vis = new bool[NODE];

    for(int i = 0; i<NODE; i++)
        vis[i] = false;    //すべてのノードを未訪問として初期化

    if(isCycle(0, vis, -1))    //閉路が存在するかどうかをチェック
        return false;

    for(int i = 0; i<NODE; i++) {
        if(!vis[i])    //探索で未訪問のノードが残っていれば、グラフは非連結
            return false;
    }
    return true;
}

int main() {
    if(isTree())
        cout << "The Graph is a Tree.";
    else
        cout << "The Graph is not a Tree.";
}

実行結果

The Graph is a Tree.

計算量

隣接行列を用いた上記の実装では、各頂点からすべての頂点を走査するため、時間計算量は O(V²) となります。隣接リストを使用すれば、時間計算量を O(V + E) まで改善できます。一方、訪問状態を管理する配列などの分、空間計算量は O(V) です。