UnionFind木の考え方

はじめに

基本的なアルゴリズムの一つであるUnionFind木についてまとめました。

UnionFind木とは？

UnionFind木とは無向グラフのノードのとエッジの情報から、どのノード同士が連結していてたどることができるかどうかを判定するアルゴリズムです。

UnionFind木のデータ構造

UnionFind木ではリストでデータを保存します。
親となるノードは-1で表し、子となるノードでは親のノード番号を指します。
例えば、5つのノードがあったとして、エッジの情報が与えられてない場合

[-1,-1,-1,-1,-1]

のような形で表すことができます。
ここでノード1とノード2が連結しているということを表したいときは、

[-2,0,-1,-1,-1]

のような形で表現できます。
無向グラフであるため明確にどちらが親というのは決まっていないため、ノード番号が若いときを親として表現します。
またノード1は-2となっていますが、親は子を新しく持った時に-1を行います。そうすることで、連結しているノードの数を表現しています。

推移的に連結している時

先ほどのグラフから新たにノード2とノード3が連結したとします。
その場合、1,2,3のノードが連結しています
この情報は

[-2,0,0,-1,-1]

このように表現できます。ノード3は直接依存しているノード2ではなくてさらにその親ノードであるノード1を指します。

Pythonの実装例

以下がPythonでの実装例です。

UnionFind.py

class UnionFind:
    def __init__(self,n):
        self.list=[-1]*n

    def find(self,index):
        while self.list[index]>=0:
            index=self.list[index]
        return index
    
    def union(self,a,b):
        x=self.find(a)
        y=self.find(b)

        if x>y:
            x,y=y,x
        
        self.list[x]+=self.list[y]
        self.list[y]=x
    
    def group_num(self):
        group=0
        for i in self.list:
            if i<0:
                group+=1
        return group