[グラフ] 素集合データ構造

以下のスライドがダントツで分かりやすいです。

素集合データ構造

素集合データ構造（そしゅうごうデータこうぞう、英: disjoint-set data structure）は、データの集合を素集合（互いにオーバーラップしない集合）に分割して保持するデータ構造。このデータ構造に対する以下の2つの便利な操作をUnion-Findアルゴリズムと呼ぶ。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

素集合データ構造は、MakeSet Find Union という操作を持ち、それぞれの集合を木構造で表します。

素集合データ構造を使うことで、「ある要素がどの集合に属するかどうか」「2つの要素は同じ集合に属しているか」というような問題を考える際に、高速に計算が行えます。

ある複数の集合が配列で保持されている時、ある要素がそれらの集合のどれに属するかを調べようとすると、単純に考えると最初から最後まで探索するので$O(N)$かかります。

平衡2分木で集合が保持されていれば$ O ( \log N)$ で探せます。

素集合データ構造で複数の集合を保持することで、この時間を償却実行時間で$ O ( \alpha (N)) $ にすることができます。

$ \alpha (N) $ はアッカーマン関数$ Ack(N, N)$の逆関数で、$N$が増えると $ \alpha (N) $ は高速で小さな数になり、 $ O ( \alpha (N)) $ は$ O(1) $のように考えることができます。

Why is the Inverse Ackermann function used to describe complexity of Kruskal’s algorithm?

素集合

2つの集合が交わりを持たない (disjoint) あるいは互いに素（たがいにそ、英語: mutually disjoint）であるとは、それらが共通の元を持たぬことをいう。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

素集合とはあまり聞きなれ言葉ですが、「互いに素である」集合のことを「互いに素集合である」と表現し、素集合データ構造は、データの集合を、「互いに素である」複数の集合で表現するものです。

償却実行時間

コンピュータサイエンスにおける 償却解析 (しょうきゃくかいせき、英語: Amortized_analysis、ならし解析ともよばれる)とは、与えられたアルゴリズムの時間計算量（英語版）または、コンピュータプログラムの文脈における資源、特に時間またはメモリをどれだけ必要とするかを分析する手法である。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

償却実行時間とは、計算量の大きい操作がまれにしか起こらないようなデータ構造において、そういった計算量の大きい操作はその他の計算量の少ない操作により「償却」されているとする計算量の考え方です。

例えばあるデータ構造の実行時間を考えた時、$N$回中$N-1$回は$ O (1) $ だが1回は$ O (N)$であるとすると、通常は実行時間を$ O (N) $ になりますが、償却実行時間では $ O (N)$ の操作が $N-1$回の操作で「少しずつ償却されている」と考えて $ O (1) $ と考えます。

アッカーマン関数

アッカーマン関数（アッカーマンかんすう、英: Ackermann function、独: Ackermannfunktion）とは、非負整数m と n に対し、
$$ \begin{eqnarray} Ack(m, n) = \begin{cases} n+1, & if \ m=0 \\ Ack(m-1, 1), & if \ n=0 \\ Ack(m-1, Ack(m, n-1)), & otherwise \end{cases} \end{eqnarray} $$
によって定義される関数のことである。
出典: フリー百科事典『ウィキペディア（Wikipedia）』

数式は難しいですが、アッカーマン関数とは、$m$と$n$がともに0の時は1ですが、 $m$や$n$が4や5という小さな数に変化しただけでとても大きな数になる関数です。

素集合データ構造の償却実行時間$ O ( \alpha (N)) $ の $ \alpha (N) $ はこのアッカーマン関数$ Ack(N, N)$の逆関数なので、$N$が4や5ぐらいの数で $ \alpha (N) $ はとても小さな数になります。

素集合データ構造の操作

素集合データ構造は、MakeSet Find Union という操作を持ちます。

素集合データ構造は、集合を木構造で表し、要素であるそれぞれのノードは、親ノードへの参照を持ちます。

それぞれの木のルートにあたるノードが、その集合を代表していると考えます。

MakeSet

1つの要素だけの集合を作ります。

ノードの親ノードを自分自身に設定するだけです。

素集合データ構造では、まず最初に、全ての要素を MakeSet で一つだけの集合として表します。

function MakeSet(x)
     x.parent := x

Find

特定の要素がどの集合に属しているか求めます。

木構造のルートが代表としてその集合を表すので、再帰でルートまでたどります。

つまり、自身の親が自分自身になったときに、そのノードがその集合を代表して表していることになります。

 function Find(x)
     if x.parent == x
        return x
     else   
        return Find(x.parent)

以下のような集合を考えて、「5」「4」「7」がそれぞれの集合の代表、木構造のルートとなっているとします。

素集合の例

find(1) find(2) find(5) find(6) find(8)は 5 を、find(3) find(4)は 4を、 find(7) は 7 を返します。

Union

2つの集合を1つに統合します。

 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

これは、片方のルートの親へのポインタをもう片方のルートへ設定するだけです。

木の平衡性の問題の解決

上記のUnionの操作では、木の結合を行っていくと木がアンバランスになってしまい、Findの操作がだんだんと遅くなってしまいます。

そこで、Unionの操作にunion by rankという考え方、Find の操作にpath compression という考え方を取り入れることで、木の平衡性を保てるようにします。

union by rank

Unionの操作を行う時、ランクの大きい木を親、小さい木を子にすることで、木の平衡を保ちます。

ランクは木の深さのことで、ルートノードの深さがその木のランクになります。

function MakeSet(x)
    x.parent := x
    # ノードはランクを持つ。
    x.rank   := 0

function Union(x, y)
    xRoot := Find(x)
    yRoot := Find(y)
    # x のランクが y のランクより大きい時は x が親
    if xRoot.rank > yRoot.rank
        yRoot.parent := xRoot
    # y のランクが x のランクより大きい時は y が親
    else if xRoot.rank < yRoot.rank
        xRoot.parent := yRoot
    # x のランクと y のランクが同じだが、x と y が別の木に属す時
    # どちらでも良いが、ここでは x を親にして、x のランクを 1 増やす。
    else if xRoot != yRoot
        yRoot.parent := xRoot
        xRoot.rank := xRoot.rank + 1

path compression

Findの操作を行う時に、親がルートになっていないノードの親を全てルートに設定することで、次回以後のFindの操作では、より平衡な木を探索できるようにします。

function Find(x)
    if x.parent != x
        x.parent := Find(x.parent)
    return x.parent

親ノードが自分自身でない限り、その木の代表であるルートを自身の親ノードに設定します。

Pythonで実装

疑似コードそのままに Python で素集合データ構造を実装します。

元のデータはVertexクラスで表し、素集合データ構造はそれぞれのデータをNodeクラスに変換して保持します。

また、英語版wikipedia にあったループを使ったfind も記述します。

以下の要素を使ってテストします。

class Vertex(object):

    def __init__(self, name):
        self.name = name
        self.node = None


class Node(object):

    def __init__(self, vertex, parent=None, rank=0):
        self.node_name = vertex.name
        self.parent = parent
        self.rank = rank


class DisjointSet(object):

    def __init__(self, vertex_list):
        self.vertex_list = vertex_list
        self.make_sets(vertex_list)

    def make_sets(self, vertex_list):
        for vertex in vertex_list:
            self.make_set(vertex)

    def make_set(self, vertex):
        node = Node(vertex, parent=None, rank=0)
        node.parent = node
        vertex.node = node

    def union(self, x_node, y_node):
        
        x_root = self.find(x_node)
        y_root = self.find(y_node)

        # in the same set
        if x_root == y_root:
            return

        if x_root.rank > y_root.rank:
            y_root.parent = x_root
        elif x_root.rank < y_root.rank:
            x_root.parent = y_root
        else:
            y_root.parent = x_root
            x_root.rank += 1

    def find(self, node):
        if node.parent != node:
            node.parent = self.find(node.parent)
        return node.parent

        ## using iteration, easeir to understand
        # current_node = node
        # while current_node.parent_node != current_node:
        #     current_node = current_node.parent_node
        # root = current_node

        # # path compression
        # current_node = node
        # while current_node != root:
        #     # swap
        #     current_node.parent_node, current_node = root, current_node.parent_node
        
        # return root

if __name__ == '__main__':
    
    v1 = Vertex('1')
    v2 = Vertex('2')
    v3 = Vertex('3')
    v4 = Vertex('4')
    v5 = Vertex('5')
    v6 = Vertex('6')
    v7 = Vertex('7')
    v8 = Vertex('8')
    vertex_list = [v1, v2, v3, v4, v5, v6, v7, v8]

    # {1}, {2}, {3}, {4}, {5}, {6}, {7}, {8}
    disjointset = DisjointSet(vertex_list)
    # 4
    print(disjointset.find(v4.node).node_name)
    # 5
    print(disjointset.find(v5.node).node_name)

    # {1, 2}, {3}, {4}, {5}, {6}, {7}, {8}
    disjointset.union(v1.node, v2.node)
    # {1, 2, 5}, {3}, {4}, {6}, {7}, {8}
    disjointset.union(v1.node, v5.node)
    
    # {1, 2, 5}, {3}, {4}, {6, 8}, {7}
    disjointset.union(v6.node, v8.node)
    # 1
    print(disjointset.find(v5.node).node_name)
    
    # {1, 2, 5}, {3, 4}, {6, 8}, {7}
    disjointset.union(v3.node, v4.node)
    # 6
    print(disjointset.find(v8.node).node_name)
    
    # {1, 2, 5, 6, 8}, {3, 4}, {7}
    disjointset.union(v2.node, v8.node)
    # 1
    print(disjointset.find(v8.node).node_name)