ALGORITHM NOTE Disjoint Sets, Union Find

Disjoint Sets, Union Find

2006.05.07 12:46 データ構造

Disjoint Sets, Union Find とは？
Disjoint Sets は、多くのデータを互いに素な集合（１つの要素が複数の集合に属することがない集合）に分類して管理するためのデータ構造です。このデータ構造は、動的に以下の操作を高速に処理します。

	makeSet( x ): 要素が x ただ１つである新しい集合を作る
	findSet( x ): 要素 x が属する集合の"代表"の要素を求めるつまり、要素 x がどの集合に属するかを調べることができる
	union( x, y ): 指定された２つの要素 x, y を unite（合併）する

Disjoint Sets に対して、「指定された２つの要素 x, y が、同じ集合に属するか？」どうかを調べる操作、つまり findSet(x) == findSet(y) は Union Find と呼ばれます。

Disjoint Sets の表現
Disjoint Sets を実装する方法はいくつかありますが、ここでは Disjoint Sets forests と呼ばれる"森"の構造を用います。森を構成する tree (木)が各集合を表し、tree の各ノードが集合内の各要素を表します。

findSet( x )
集合を区別するために、各 tree の根を代表 (representative) とし、集合を識別するために用います。従って、findSet( x ) は、要素 x が属する tree （集合）の根を値として返します。これを実現するために、各ノードはそれ自身から代表まで到達できるように、親へのポインタを持ちます（ただし、代表はそれ自身へのポインタを持ちます）。

例えば、下図の Disjoint Sets で findSet( 5 ) の結果は 1 、findSet( 0 ) の結果も 1 なので、5 と 0 が同じ集合に属することが分かります。

findSet( x ) の計算量は、各ノードから代表までの間にたどるポインタの数 = 木の高さです。ここで、findSet( x ) は、単に代表を求めるだけではなく、次に実行される findSet( x ) の効率を高めるために、ある工夫をしています。それは、ある要素の代表を求めるとき、その要素から代表に至る経路の全てのノードについて、ポインタが直接代表を指すように変更します。例えば、下図はある集合 S に対して findSet( 0 ) を実行した結果を示しています。

S		S'
	→ findSet( 0 ) →

S において、各ノードは親へのポインタをもち、要素 0 の代表は、0 → 1 → 2 → 3 → 4 とたどることによって 4 と求められます。その経路上のノードのポインタを直接 4 を指すように処理し S' を得ます。

この工夫によって、極めて高さの低い木が生成されることがわかります。つまり、次回実行されるであろう S' に属する要素 x における findSet( x ) の操作は極めて少ない計算量で行うことができます。これを path compression (経路圧縮)といいます。

再帰を用いて path compression を行う findSet の実装は、以下のようになります。

    int findSet( int x ){
        if ( x != p[x] ) p[x] = findSet( p[x] );
        return p[x];
    }

union( x, y )
指定された２つの要素 x, y を合併する操作は、x の代表と y の代表を求め、どちらか一方を新しい代表として選びます。つまり、代表にならなかったほうのポインタを新しい代表を指すように更新します。例えば、下図はある Disjoint Sets S に対して union( 2, 4 ) を実行した結果を示しています。

S		S'
	→ union( 2, 4 ) →

ここで重要なことが、"どちらの代表を新しい代表として選ぶか"です。ポイントは、合併する集合を表す木の高さです。低い方の木を高い方の木に合併すれば、新しい木の高さが高くなることはありません。従って、高い木の代表を新しい代表にします。各ノード x を根としたときの木の高さに関する情報を rank[x] という変数に記録します。１つの要素が１つの集合を成している初期状態では、rank[x] は全て 0 としておきます。そして同じ rank の木を合併するときに rank を１つ増やします。以下に例を示します。

S		S'
	→ merge( 0, 5 ) →

S		S'
	→ merge( 0, 5 ) →

merge や経路圧縮を伴う findSet によって、rank の値は変化していきます。従って、rank は木の正確な高さを与えるものではなく、木の高さの上限を与えます。

以下に、DisjointSets のデータ構造を実装したプログラムを示します。

class DisjointSet{
    public:
    DisjointSet(){}
    DisjointSet( int size ){
        rank.resize( size, 0 );
        p.resize( size, 0 );
    }
    
    void makeSet( int x ){
        p[x] = x;
        rank[x] = 0;
    }
    
    void union( int x, int y ){
        link( findSet(x), findSet(y) );
    }
    
    int findSet( int x ){
        if ( x != p[x] ) p[x] = findSet( p[x] );
        return p[x];
    }
    
    bool isSameSet( int x, int y ){
        return ( findSet(x) == findSet(y) );
    }
    
    private:
    vector<int> rank, p;
    
    void link ( int x, int y ){
        if ( rank[x] > rank[y] ){
            p[y] = x;
        } else {
            p[x] = y;
            if ( rank[x] == rank[y] ) rank[y]++;
        }
    }
};