Union-Find木

  • 要素が $n$ 個あり、各要素は互いに素なグループに1つだけ属する
    • 例: 生徒は必ず何かのクラブ活動に入り、兼部は認められていない
  • グループは統合される可能性があるが、分割はされない

という前提で、

  • ${\rm Unite}(x, y)$: 要素xの属するグループと、yの属するグループを統合する
  • ${\rm Find}(x, y)$: 要素xとyが同じグループに属するか調べる

という2つのクエリを効率的に処理するのが、Union-Find木

Disjoint Set Union、略してDSUともいう。

アルゴリズム

  • 各グループの要素から、“代表”を1つ決める
  • 代表以外の要素は、“親”となる要素を1つずつ持つ
    • どの要素からでも、親の親の親……を辿っていけば自身の代表に着くようにする
    • つまり、グループを、代表を根とした木構造で表現する
    1    4    8    ←1,4,8が代表
  ↗↑    ↑
 2 5    6          ←2や5の親は1, 3の親は2
 ↑     ↗  ↖
 3    7    9

これをもとに、先ほどの2つの操作を言い換えると、以下のようになる。

  • ${\rm Unite}(x, y)$は、一方の代表を、もう一方の代表につなぐ(親子にする)
  • ${\rm Find}(x, y)$は、xとyから親を辿って同じ代表に行き着くか調べる

高速化の工夫

  • 木の階層を低く保たないと、代表を見つける処理に時間がかかる
    • 以下の例、はやい例では2~4のどの要素からも、1回調べたら代表にたどり着ける
    • おそい例では、4からだと、4→3→2→1と3回辿らないと代表に着かない
    • できるだけ、はやい例のような状態を保ちたい
◎はやい  ×おそい
   1        1
 ↗↑↖      ↑
2 3 4     2
             ↑
             3
             ↑
             4

経路圧縮

  • 一度調べた経路上にある要素は、全て親を代表に書き換える
    • おそい例において、一度UniteやFindクエリによって4→3→2→1と調べて1が代表だとわかったら、2~4の親を1に書き換える

ランク

  • 木の最大深さ(ランク)を記録しておく
  • Union時、ランクの低い方のグループを、高い方のグループにつなぐ
    • 互いのランクが等しい場合を除き、ランクが高くならずに済む(等しい場合のみ1増える)
この2つをUnionする場合| こうすると   | 低い方に高い方をつなげると
 Rank:2    Rank:4     | Rank:4のまま | Rank:5になっちゃう
   1        5       |      5      |     1
 ↗↑↖      ↑       |      ↑↖    | ↗↗↑↖
2 3 4     6       |      1 6   |23 4 5
             ↑       |  ↗↗↑ ↑   |        ↑
             7       | 23 4 7   |        6
             ↑       |         ↑   |        ↑
             8       |         8   |        7
                      |              |        ↑
                      |              |        8

計算量

上記の2つの改善を行って、unite, find 1回にかかる計算量はいずれも $O(\alpha(N))$ となる(らしい)。

これはいずれもならし計算量で、何回もやると平均がこの値に近づいていく。

ただし $\alpha(N)$ はアッカーマン関数 $\rm{Ack}(N,N)$ の逆関数で、$N$ が少し大きくなると急速に小さくなるので、ほとんど定数と考えてよい。

実装

  • 要素数 $n$ の配列tableを作り、-1で初期化する
    • ${\rm table}[x]$ が負ならば、$x$ は代表。絶対値はランクを示す
    • ${\rm table}[x]$ が非負ならば、$x$ は代表でない。値は $x$ の親を示す
    • 最初は、$n$ 個の要素が別々の $n$ 個のグループに所属している状態
  • rootで代表を再帰的に探索する
    • ついでに経路圧縮を行う
2020/05 rootを非再帰に変更(特にPyPyで高速化)

unite()のd1,d2は実際の値を正負逆転させているので、大小関係に注意。

# Python3

class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n

    def root(self, x):
        stack = []
        tbl = self.table
        while tbl[x] >= 0:
            stack.append(x)
            x = tbl[x]
        for y in stack:
            tbl[y] = x
        return x

    def find(self, x, y):
        return self.root(x) == self.root(y)

    def unite(self, x, y):
        r1 = self.root(x)
        r2 = self.root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2


if __name__ == '__main__':
    ins = UnionFind(4)
    ins.unite(0, 1)
    ins.unite(2, 3)
    print(ins.find(0, 3))  # False
    ins.unite(1, 2)
    print(ins.find(0, 3))  # True

亜種

ランクを要素数とする

ランクは木の深さでなく、要素数で考えることもある。

  • 例: 要素数100,最大深さ2のグループAと、要素数5,最大深さ4のグループB
    • AにBを繋ぐとBの5個の要素の深さが1ずつ増え、最大深さは5
    • BにAを繋ぐとAの100個の要素の深さが1ずつ増え、最大深さは4
    • 局所的に最大深さが深くなろうが、100個の要素の深さが1ずつ増える方が効率悪くない?という考え方か
  • A.V.Aho, John E. Hopcroft, Jeffrey D. Ulman, 『データ構造とアルゴリズム』, 培風館, 1987

実際、どちらを選んでも速度は体感できるほど変わらない。

木の深さってあまり使い道が無いが、「$x$ が含まれるグループの要素数」は任意の時点で取得できると嬉しい場合はある。
よって、ランクは要素数としておいた方が、何かと便利かも知れない。

実装

unite()の中身が少し変化する。また、get_size()を追加。

Python3

グループの要素も保持

上記の例では、グループの要素数はわかっても、具体的に現時点でのグループにはどの要素があるのか、というのはわからない。

グループの要素も管理したい場合、tableとは別にもう1つグループを管理する配列も用意して、実際に統合していく。
unite()部分のならし計算量は、$O(\alpha(N))$ から $O(\alpha(N) \log{N})$ になる。

  • $x$ が含まれるグループの要素を得たいときは、配列で $x$ の根の位置を参照する
    • いったん根じゃなくなった要素はもう参照されないので、更新しなくてよい
  • unite()でグループを統合する際は、2つのグループの要素数を比較して、大きい方へ小さい方を統合する

実装

Python3

programming_algorithm/data_structure/union_find_tree.txt · 最終更新: 2021/01/31 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0