Union-Find木で無向グラフに閉路があるかを判定する

2021-12-12 c++algorithm

Union-Find木

Union-Find木はいくつかの素集合の木を持つデータ構造で、 2つの集合を結合するUnionと、要素の含まれる集合を特定し2つの要素が同じ集合に含まれるかを判定できるFindを、ならし計算量 O(α(n)) (α(n) はアッカーマン間数 A(n,n) の逆関数で log(n) よりも小さい)で行うことができる。

Unionはなるべく木が平衡になるようrankが小さい方の木が下に来るように辺を張る。1要素の木のrankは0で、同じrankの木を結合すると上にした木のrankが1増える。 Findは根の値を比較した後、辿ったノードから根へ辺を張り直して次回以降の処理を効率的に行えるようにする。

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

class union_find_tree {
    unordered_map<int, int> parent;
    unordered_map<int, int> rank;

public:
    union_find_tree(vector<int> values) {
      for(int i = 0; i < values.size(); i++) {
        parent[values[i]] = values[i];
        rank[values[i]] = 0;
      }
    }
  
    int find(int x) {
      if (parent[x] == x) return x;
      int root = find(parent[x]);
      parent[x] = root;
      return root;
    }

    void unite(int x, int y) {
      x = find(x);
      y = find(y);
      if (x == y) return;
      if (rank[x] > rank[y]) {
        parent[y] = x;
      } else {
        parent[x] = y;
        if (rank[x] == rank[y]) rank[y]++;
      }
    }

    bool same(int x, int y) {
      return find(x) == find(y);
    }
};

int main() {
  auto tree = new union_find_tree({1,2,3,4,5,6});
  tree->unite(2, 3);
  tree->unite(1, 2);
  tree->unite(4, 5);
  tree->unite(5, 6);
  cout << tree->same(2, 5) << endl; // 0
  tree->unite(2, 5);
  cout << tree->same(2, 5) << endl; // 1
}

Union-Find木による無向グラフの閉路の判定

無向グラフの辺をUnion-Find木に入れると、すでに到達可能なノードは同じ集合に属することになるので、辺を張った時に閉路ができるかを判定できる。

int main() {
  auto tree = new union_find_tree({1,2,3});
  if (!tree->same(1, 2)) tree->unite(1, 2);
  if (!tree->same(2, 3)) tree->unite(2, 3);
  if (!tree->same(3, 1)) tree->unite(3, 1); // detects the creation of a cycle
}

コストが小さい順に辺をソートし、繋げたときに閉路ができないものを採用していくことで、コストの和が最小の連結グラフである最小全域木を作るクラスカル法で用いられる。

辺ごとにUnionとFindを行うので、辺の数を |E|、ノードの数を |V| とすると計算量は O((|E|+|V|)α(|V|)) となり、深さ優先探索(DFS)や幅優先探索(BFS)で同じ所に戻ってくる経路を探す場合の O(|E|+|V|) より遅いことになるが、α(|V|) の影響はとても小さいのでほとんど問題にならないと思われる。