Union-Find木

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

という前提で、

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

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

アルゴリズム

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

経路圧縮

  • 一度調べた経路上にある要素は、全て親を代表に書き換える
    • おそい例において、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

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

  • 例: 要素数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

実装

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

# Python3

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

    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]

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

    def union(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.union(0, 1)
    ins.union(2, 3)
    print(ins.find(0, 3))  # False
    ins.union(1, 2)
    print(ins.find(0, 3))  # True

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