Union-Find

蟻本p.81

Union-Find

グループを表すデータ構造の1つ。Disjoint Set Union (DSU) とも呼ばれる。
以下の操作を高速に実現する。

  • ある要素がどのグループに属しているかを調べる (find)

  • 2つのグループを併合する (union)

原理

Union-Find木では、できるだけ木の高さが小さくなるようにノードの繋ぎ変えを行うことで、検索の高速化を実現している。
例えば、次のような \(6\) つの要素に対してunion, findそれぞれの操作を考えてみる。
union_find_init
unionでは、後述するfind操作によりそれぞれの親を調べた後、一方の親にまとめる。
この状態ではまだ、木の高さは最適化されていないことに注意。
union_find_union
findでは、ノードの親を調べる。
このとき、findを再帰的に呼び出す過程で、通過したノードの親を繋ぎ変えるようにする。
この繋ぎ変えにより、findの呼び出しで通過した部分木の高さは高々1になり、次回以降のfindが高速化される。
union_find_find

実装

[1]:

class UnionFind():
    """Union-Find木の実装
    """

    def __init__(self, n):
        self.n = n
        self.parent = [x for x in range(n)]

    def find(self, x):
        """要素xが所属するグループを返す
        """
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]

    def union(self, x, y):
        """要素x, yがそれぞれ所属するグループを併合する
        """
        x = self.find(x)
        y = self.find(y)
        if x > y:
            x, y = y, x
        self.parent[y] = x

    def parents(self):
        """全てのノードについて、対応する親ノードを返す"""
        return [self.find(x) for x in range(self.n)]

[2]:

N = 6
uf = UnionFind(N)
uf.union(0, 1)
uf.union(5, 4)
uf.union(2, 4)
print(uf.parents())

[0, 0, 2, 3, 2, 2]