2.5 集合族の併合

2.5 集合族の併合

数理情報系 4 年

甲本健太

2.5 集合族の併合

目次

  1. 問題の定義
    1. 例
  2. 配列による実現
    1. MERGE の工夫
  3. 木による実現
    1. 路の圧縮
  4. 全体での計算量
  5. 実装例
  6. まとめ
2.5 集合族の併合

問題の定義

互いに素な複数の集合を併合 (merge) していくプロセスが色々な計算に現れる．
(c.f. クラスカル法)

ここで，問題を抽象化し，次の 2 つの操作ができる構造（素集合データ構造）を考える．

  1. MERGE(Si,Sk)\mathrm{MERGE}(S_i, S_k)：
    Si∩Sk=∅S_i\cap S_k = \varnothing のとき，Si∪SkS_i\cup S_k を作り，その名前を SiS_i または SkS_k と定める．
  2. FIND(x)\mathrm{FIND}(x)：
    xx を含む集合名を返す．xx がどの集合にも属していなければ定義されない．
2.5 集合族の併合

問題の定義（例） (1/2)


center

2.5 集合族の併合

問題の定義（例） (2/2)


center

2.5 集合族の併合

配列による実現 (1/2)

簡単のため，

  • 要素 jj を集合 {0,1,…,N−1}\{0,1,\ldots,N-1\} から
  • 集合名 SiS_i の添字 ii を {0,1,…,M−1}\{0,1,\ldots,M-1\} から

それぞれ選ぶとする．

単純な実装

最も単純な実装方法は，右の図のように配列 set_name\mathrm{set\_name} を用意し，
j∈Sij\in S_i を set_name[j]=i\mathrm{set\_name}[j] = i によって表すことである．

このとき，計算量は次ページのようになる．

2.5 集合族の併合

配列による実現 (2/2)

FIND

FIND(j)\mathrm{FIND}(j) をする際には，set_name[j]\mathrm{set\_name}[j] の番号を読むだけで良い．
→\to 定数時間で実行可能

MERGE

MERGE(Si,Sk)\mathrm{MERGE}(S_i, S_k) を実行するには，

for j in range(N):         # すべてのjに対し，
    if set_name[j] == i:   #   集合名が S_i の集合を見つけたとき
        set_name[j] = k    #   集合名を S_k に更新

を実行しなければならない．→\to 時間計算量は O(N)O(N)

2.5 集合族の併合

配列による実現 （MERGE の工夫） (1/4)


各集合を右の図のように 2 つの配列 set\mathrm{set} と element\mathrm{element} を用意して表現する．

  • 配列 set\mathrm{set}
    • size[i]\mathrm{size}[i]：位数 ∣Si∣|S_i|
    • first[i]\mathrm{first}[i]：SiS_i の最初の要素のポインタ
      （first[i]=−1\mathrm{first}[i] = -1 は Si=∅S_i = \varnothing を意味する）
  • 配列 element\mathrm{element}
    • set[j]\mathrm{set}[j]：その要素 jj を含む SiS_i の添字 ii
    • next[j]\mathrm{next}[j]：jj の次の要素へのポインタ

このとき，計算量は次ページのようになる．


2.5 集合族の併合

配列による実現 （MERGE の工夫） (2/4)


FIND

FIND(j)\mathrm{FIND}(j) をする際には，element.set[j]\mathrm{element.set}[j] の番号を読むだけで良い．
→\to 定数時間で実行可能

MERGE

MERGE(Si,Sk)\mathrm{MERGE}(S_i, S_k) を行う．新しい集合名を SkS_k とするとき，以下のアルゴリズムを用いる

  1. SiS_i の最後の要素 ll を element.next\mathrm{element.next} をたどって求め， next[l]\text{next}[l] を SkS_k の最初の要素にする．
    このとき同時に，element.set[j]←k\mathrm{element.set}[j] \leftarrow k としておく．
  2. 配列 set\mathrm{set} を以下のように更新する．

    set.size[k]=set.size[i]+set.size[k];set.first[k]=set.first[i];set.size[i]=0; set.first[i]=−1;// Si を空集合に更新\begin{align*} &\mathrm{set.size}[k] = \mathrm{set.size}[i] + \mathrm{set.size}[k];\\ &\mathrm{set.first}[k] = \mathrm{set.first}[i];\\ &\mathrm{set.size}[i] = 0; ~\mathrm{set.first}[i] = -1; &// ~S_i~ \text{\small を空集合に更新} \end{align*}

所要時間は O(∣Si∣)O(|S_i|) である．

2.5 集合族の併合

配列による実現 （MERGE の工夫） (3/4)

マージの際に以下のような工夫をすると，全体の計算量を大きく減らすことができる．

SiS_i と SkS_k を併合する際，常に小さい方の集合名を大きい方に修正することにする．
このとき要素すべてを併合するのに要する時間は O(Mlog⁡2N)O(M \log_2 N) 時間である．

証明
要素 jj に注目し，jj が所属する集合が変更される回数を考える．jj が所属する集合がマージされ，jj の所属が変更されるとき，jj が所属する集合の大きさは 22 倍以上になる．よって，全体の要素数が NN のとき，要素 jj の移動は高々 ⌊log⁡2N⌋\lfloor\log_2 N\rfloor 回しか行われない．
併合の回数が最大 M−1M-1 回であることを考慮すると，全体では O(Mlog⁡2N)O(M\log_2 N) 時間である

2.5 集合族の併合

配列による実現 （MERGE の工夫） (4/4)


連結リストのように表記すると以下のようになる．

center

2.5 集合族の併合

木による実現 (1/2)


集合 SiS_i に所属するすべての要素を一つの木の節点として表し．そのような集合族を森のように実現することもできる．（先ほどとポインタの向きが逆なことに注意）


center

2.5 集合族の併合

木による実現 (2/2)

FIND

FIND(j)\mathrm{FIND}(j) を行うときは，節点 jj から根までたどれば集合名がわかる．
→ 所要時間は jj の深さに比例するが，要素数 NN の対数で抑えられる．

SiS_i と SkS_k を併合するとき，常に小さい方を大きい方の子節点として加えていくことにする．このとき FIND(j)\mathrm{FIND}(j) 1 回の計算量は O(log⁡2N)O(\log_2 N) である．

証明
節点 jj が併合され，高さが変更されるとき，jj を含む集合の大きさは 22 倍以上になるため，jj の高さは高々 ⌊log⁡2N⌋\lfloor\log_2 N\rfloor 回しか変更されない．一回の併合により節点の高さは 11 しか増えないことから，計算の途中で得られる任意の木 SiS_i の高さは ⌊log⁡2N⌋\lfloor\log_2 N\rfloor 以下である．

2.5 集合族の併合

路の圧縮


さらに，FIND(j)\mathrm{FIND}(j) を行うときに，節点 jj から根へのパス上にある節点をすべて根の子とする路の圧縮と呼ばれる操作を行うとより高速になることが知られている．

center

2.5 集合族の併合

全体での計算量



併合の工夫と路の圧縮を同時に行った場合，MERGE,FIND\mathrm{MERGE},\mathrm{FIND} をどのような順序で行っても mm 回の FIND\mathrm{FIND} 操作を O(mα(m,N))O(m\alpha(m,N)) 時間で実行できる．
→\rightarrow よって，併合全体の計算量は O(Nα(N))O(N\alpha(N)) 時間となる．

ただし α(m,N)\alpha(m,N) はアッカーマン関数の逆関数であり，非常にゆっくりと増加する．

例として，アッカーマン関数 AA について，A(4,3)=2265536−3A(4,3) = 2^{2^{65536}} - 3 である．[1]

[1] https://ja.wikipedia.org/wiki/アッカーマン関数

2.5 集合族の併合

実装例



Python による実装は右の通り．

find 関数

1 つ目のwhile文で根を見つけ，2 つ目のwhile文で路の圧縮を行っている．

merge 関数

集合 i,ji,j の根をそれぞれfindで調べ，
∣Si∣>∣Sj∣|S_i| > |S_j| だった場合に i,ji,j を交換することで，常に大きい集合（∣Sj∣|S_j|）にマージするようにしている．

class UnionFind:
    def __init__(self, N):
        self._parent = list(range(N))
        self._size = [1] * N

    def find(self, i) -> int:
        p = i
        while self._parent[p] != p:
            p = self._parent[p]
        # 路の圧縮
        while self._parent[i] != i:
            i = self._parent[i]
            self._parent[i] = p
        return p

    def merge(self, i, j):
        i = self.find(i)
        j = self.find(j)
        if self._size[i] > self._size[j]:
            i, j = j, i
        # 併合
        self._parent[i] = j
        self._size[j] += self._size[i]
        self._size[i] = 0
2.5 集合族の併合

まとめ

  • 集合族に対して「集合同士のマージ」，「要素の所属する集合の取得」という操作を行う問題は，クラスカル法をはじめとして様々なアルゴリズムで登場する
  • このような問題は，素集合データ構造と呼ばれるデータ構造を用いて効率的に処理できる
  • 各集合を木として管理することで，「併合の工夫」，「路の圧縮」を行うことができ，併合全体の計算量を O(Nα(N))O(N\alpha(N)) にすることができる．