トップ > 無向・有向グラフにおける閉路検出方法

無向・有向グラフにおける閉路検出方法

競技プログラミングでは「グラフの閉路検出」は頻出です。 しかし，解法が複数あるため，実践において時々どうアプローチしようか迷ったりすることがあります（個人的に......）。 本記事では，本番で適当な方法を選択できるように「無向・有向グラフにおける閉路検出方法」についてまとめます。

無向グラフ

無向グラフにおいて，閉路がないグラフは，木である連結成分が1つまたは複数（森）ある状態です。

方法(1)：DFS（深さ優先探索）

ある連結成分において，任意の頂点を根として選択し，DFSを行います。 そのDFSの途中で，ある頂点に再度訪問した場合，その連結成分には閉路があると判断できます。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;  // n:=(グラフの頂点数), m:=(辺の数).
    cin >> n >> m;

    vector<vector<int> > g(n);  // g[v][]:=(頂点vの隣接リスト).
    for(int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
        // 頂点uとvに辺を張る。
        g[u].push_back(v);
        g[v].push_back(u);
    }

    bool seen[n] = {};  // seen[v]:=(頂点vを訪問したか).
    auto dfs = [&g, &seen](auto self, int u, int p) -> bool {
        seen[u] = true;
        for(auto v : g[u]) {
            if(v == p) continue;      // DFS木において頂点vが親の場合.
            if(seen[v]) return true;  // 頂点vがすでに訪問している場合。閉路ありと判断する。
            if(self(self, v, u)) return true;
        }
        return false;
    };

    for(int i = 0; i < n; ++i) {
        if(!seen[i]) {  // まだ未探索の連結成分がある場合。
            auto res = dfs(dfs, i, -1);
            if(res) {
                cout << "Find cycle" << endl;
                return 0;
            }
        }
    }

    cout << "No cycle" << endl;
}

方法(2)：Union-Find

Union-Find木を用い，各頂点を管理します。 グラフの辺リストを走査し，辺を結ぶ2頂点を連結していきます。 この走査の途中で，2頂点がすでに連結である場合，閉路があると判断できます。

#include <bits/stdc++.h>
using namespace std;

// 素集合データ構造。
class UnionFind {
    int m_vn;                // m_vn:=(ノード数).
    int m_gn;                // m_gn:=(連結成分数).
    std::vector<int> m_par;  // m_par[v]:=(ノードvの親番号). 0未満の場合，vは根であり，値の絶対値は連結成分のサイズを表す。

public:
    UnionFind() : UnionFind(0) {}
    explicit UnionFind(size_t vn) : m_vn(vn), m_gn(vn), m_par(vn, -1) {}

    // ノードの総数を返す。
    int vn() const { return m_vn; };
    // 連結成分の数を返す。
    int gn() const { return m_gn; };
    // ノードvが属する連結成分の根番号を返す。
    int root(int v) {
        assert(0 <= v and v < vn());
        if(m_par[v] < 0) return v;
        return m_par[v] = root(m_par[v]);
    }
    // ノードvが属する連結成分のサイズを返す。
    int size(int v) {
        assert(0 <= v and v < vn());
        return -m_par[root(v)];
    }
    // ノードuとvが連結しているか判定する。
    bool is_same(int u, int v) {
        assert(0 <= u and u < vn());
        assert(0 <= v and v < vn());
        return root(u) == root(v);
    }
    // ノードuとvの属する連結成分を繋げる。
    bool unite(int u, int v) {
        assert(0 <= u and u < vn());
        assert(0 <= v and v < vn());
        u = root(u), v = root(v);
        if(u == v) return false;                // Do nothing.
        if(size(u) < size(v)) std::swap(u, v);  // Merge technique.
        m_par[u] += m_par[v];
        m_par[v] = u;
        m_gn--;
        return true;
    }
    void reset() {
        m_gn = vn();
        std::fill(m_par.begin(), m_par.end(), -1);
    }
};

int main() {
    int n, m;  // n:=(グラフの頂点数), m:=(辺の数).
    cin >> n >> m;

    vector<pair<int, int> > edges(m);  // edges[]:=(頂点firstとsecondを繋ぐ辺のリスト).
    for(auto &[u, v] : edges) {
        cin >> u >> v;
        assert(0 <= u and u < n);
        assert(0 <= v and v < n);
    }

    UnionFind uf(n);
    for(const auto &[u, v] : edges) {
        if(uf.is_same(u, v)) {  // 頂点uとvがすでに連結の場合。閉路ありと判断する。
            cout << "Find cycle" << endl;
            return 0;
        }
        uf.unite(u, v);
    }

    cout << "No cycle" << endl;
}

有向グラフ

有向グラフにおいて，閉路がないグラフはDAG (Directed Acyclic Graph) です。

方法(3)：トポロジカルソート

DAGであればトポロジカルソートが可能です。 つまり，トポロジカルソートができなければDAG（閉路のないグラフ）ではありません（対偶）。

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;  // n:=(グラフの頂点数), m:=(辺の数).
    cin >> n >> m;

    vector<vector<int> > g(n);  // g[v][]:=(頂点vが始点となる辺のリスト).
    vector<int> deg(n, 0);           // deg[v]:=(頂点vの入次数).
    for(int i = 0; i < m; ++i) {
        int from, to;
        cin >> from >> to;
        assert(0 <= from and from < n);
        assert(0 <= to and to < n);
        g[from].push_back(to);
        deg[to]++;
    }

    // トポロジカルソート。
    vector<int> res;  // res[]:=(トポロジカルソートの結果).
    queue<int> que;
    for(int i = 0; i < n; ++i) {
        if(deg[i] == 0) que.push(i);
    }
    while(!que.empty()) {
        auto u = que.front();
        que.pop();
        res.push_back(u);

        for(auto v : g[u]) {
            if(--deg[v] == 0) que.push(v);
        }
    }

    for(auto elem : deg) {
        if(elem > 0) {  // 並べていない頂点がある場合。閉路があると判断できる。
            cout << "Find cycle" << endl;
            return 0;
        }
    }

    cout << "No cycle" << endl;
}

以上，無向グラフと有向グラフ合わせて，3つの方法をまとめました。 他にも方法はあると思いますが，これだけ覚えておけば何とかなる？と思います。 しらんけど。

参考文献