DFSを使って無向グラフが木（ツリー）かどうかを判定するC++プログラム

グラフが「木（ツリー）」であるための条件は、閉路（サイクル）を一切含まないことです。この記事では、深さ優先探索（DFS）を活用して、無向グラフが木かどうかを判定するC++プログラムを紹介します。

木とは何か

木とは、閉路を持たない連結グラフのことです。n個の頂点からなる木は、必ずn−1本の辺を持ちます。したがって、グラフの中にサイクルが1つでも存在すれば、そのグラフは木ではありません。この性質を利用し、DFSによってサイクルの有無を検出することで、グラフが木かどうかを判定できます。

アルゴリズム

サイクル検出の流れは以下の通りです。

開始
関数 cyclicUtil() :
　A) 現在のノードを訪問済みとしてマークする。
　B) この頂点に隣接するすべての頂点に対して再帰的に処理する。
　C) 隣接頂点が未訪問であれば、その頂点について再帰呼び出しを行う。
　D) 隣接頂点が訪問済みであり、かつ現在の頂点の親でない場合は、サイクルが存在する。
終了
開始
関数 cyclic() :
　A) すべての頂点を未訪問として初期化する。
　B) 再帰関数 cyclicUtil() を呼び出し、それぞれのDFS木においてサイクルを検出する。
終了

サンプルコード

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class G {
    int n;
    list<int> *adj;
    bool CyclicUtil(int v, bool visited[], int par);
public:
    G(int n); // コンストラクタ
    void addEd(int v, int w);
    bool cyclic();
};
G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}
void G::addEd(int v, int u) // グラフに辺を追加する {
    adj[v].push_back(u); // vのリストにuを追加
    adj[u].push_back(v); // uのリストにvを追加
}
// visited[] を使って、頂点vから到達できる部分グラフ内のサイクルを検出する再帰関数
bool G::CyclicUtil(int v, bool visited[], int par) {
    visited[v] = true; // 現在のノードを訪問済みとしてマーク
    // この頂点に隣接するすべての頂点に対して再帰的に処理する
    list<int>::iterator i;
    for (i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i]) { // 隣接頂点が未訪問なら、その頂点に対して再帰呼び出し
            if (CyclicUtil(*i, visited, v))
                return true;
        }
        // 隣接頂点が訪問済みで、かつ現在の頂点の親でない場合、サイクルが存在する
        else if (*i != par)
            return true;
    }
    return false;
}
// グラフが木かどうかを判定する
bool G::cyclic() {
    bool *visited = new bool[n]; // すべての頂点を未訪問として初期化する
    for (int i = 0; i < n; i++)
        visited[i] = false;
    // 再帰関数 CyclicUtil() を呼び出し、異なるDFS木ごとにサイクルを検出する
    for (int u = 0; u < n; u++)
        if (!visited[u])
            if (CyclicUtil(u, visited, -1))
                return true;
    return false;
}
int main() {
    G g1(4);
    g1.addEd(0, 1);
    g1.addEd(1, 2);
    g1.cyclic() ? cout << "Undirected Graph isn't a tree\n" : cout
    << "Undirected Graph is a tree\n";
    return 0;
}

実行結果

Undirected Graph is a tree

解説のポイント

• 親頂点の扱い： DFSでは、直前の頂点（親）へ戻る辺はサイクルとはみなしません。そこで引数 par で親頂点を管理し、訪問済みの隣接頂点が親以外であった場合にのみサイクルと判断します。
• 非連結グラフへの対応： cyclic() 内で全頂点をループし、未訪問の頂点から新たにDFSを開始することで、グラフが複数の連結成分に分かれている場合にも対応できます。
• 計算量： 各頂点と各辺を高々1回ずつ調べるため、時間計算量は O(V + E) です。

なお、厳密には木であるためには「閉路がない」ことに加えて「グラフ全体が連結である」ことも必要です。DFSの開始が1回だけで済んだ場合は連結と判定できるため、このチェックを組み合わせるとより正確な判定が可能になります。