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

グラフは、サイクル（閉路）を一切含まない場合に「木（ツリー）」であるとみなされます。本記事では、DFS（深さ優先探索）を利用して、有向グラフが木かどうかを判定するC++プログラムを解説します。

アルゴリズムの概要

サイクルの検出には、「訪問済みフラグ」と「再帰スタック」の2つの配列を用います。ある頂点から探索を進めた際、現在の探索経路上（再帰スタック上）にすでに存在する頂点へ戻ってきた場合、そこにサイクルが存在すると判断できます。

Begin
function cyclicUtil() :
    a) 現在のノードを「訪問済み」かつ「再帰スタックの一部」としてマークする
    b) この頂点に隣接するすべての頂点に対して再帰的に探索を行う
    c) 探索完了後、その頂点を再帰スタックから取り除く
function cyclic() :
    a) すべての頂点を「未訪問」かつ「再帰スタック外」として初期化する
    b) 各頂点を起点に CyclicUtil() を呼び出し、サイクルの有無を検出する
End

サンプルコード

#include<iostream>
#include <list>
#include <limits.h>
using namespace std;
class G {
    int n;
    list<int> *adj; // 隣接リストを保持
    bool CyclicUtil(int v, bool visited[], bool *rs);
    public:
        G(int V); // コンストラクタ
        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 を追加
}
bool G::CyclicUtil(int v, bool visited[], bool *recurS) {
    if (visited[v] == false) {
        visited[v] = true; // 現在のノードを訪問済み・再帰スタック入りとしてマーク
        recurS[v] = true;
        // この頂点に隣接するすべての頂点に対して再帰的に探索
        list<int>::iterator i;
        for (i = adj[v].begin(); i != adj[v].end(); ++i) {
            if (!visited[*i] && CyclicUtil(*i, visited, recurS))
                return true;
            else if (recurS[*i])
                return true;
        }
    }
    recurS[v] = false; // 頂点を再帰スタックから取り除く
    return false;
}
// グラフが木かどうかを判定する
bool G::cyclic() {
    // すべての頂点を未訪問・再帰スタック外として初期化
    bool *visited = new bool[n];
    bool *recurS = new bool[n];
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        recurS[i] = false;
    }
    // 各頂点を起点に CyclicUtil() を呼び出してサイクルを検出
    for (int i = 0; i < n; i++)
        if (CyclicUtil(i, visited, recurS))
            return true;
    return false;
}
int main() {
    G g(4);
    g.addEd(0, 2);
    g.addEd(1, 2);
    g.addEd(2, 0);
    g.addEd(3, 2);
    if (g.cyclic())
        cout << "有向グラフは木ではありません";
    else
        cout << "有向グラフは木です";
    return 0;
}

実行結果

有向グラフは木ではありません

プログラムのポイント

• 隣接リスト： list<int> の配列で各頂点の隣接頂点を管理しています。
• 再帰スタックの活用： 単純な訪問済みチェックだけでは検出できない「探索中の経路への戻り」を、recurS 配列によって正確に捉えます。
• 計算量： 頂点数を V、辺数を E とすると、時間計算量は O(V + E) です。

このサンプルでは頂点 0 → 2 → 0 という閉路が存在するため、プログラムは「有向グラフは木ではありません」と出力します。閉路を取り除けば、同じコードで木であることを正しく判定できます。