Union by Rankによる効率化

Union-Findデータ構造は、集合の管理や動的な結合に非常に便利です。特に、Union by Rankは、データ構造の性能を向上させるための手法の一つです。この教材では、Union by Rankの概念を学び、Pythonでの実装を通じて理解を深めていきます。

Union-Findデータ構造の基礎

Union-Findは、以下の2つの基本操作を提供します。

1. Find: ある要素が属する集合の代表元を見つける。
2. Union: 2つの集合を結合する。

Union by Rankの概念

Union by Rankのアイデアは、結合する際に常に低いランクの木を高いランクの木の下に置くことです。これにより、木の高さが小さく保たれ、Find操作の効率が向上します。

• Rank: 木の高さを表します。
• 2つの集合を結合する際、ランクが小さい方をランクが大きい方に結合します。

実装

以下に、Union-Findデータ構造をUnion by Rankを用いて実装します。

class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [1] * size  # 各ノードの初期ランクは1

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # パス圧縮
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP != rootQ:  # 2つの要素が異なる集合に属している場合
            # ランクに基づいて結合
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1  # ランクを1増やす

# 使用例
if __name__ == "__main__":
    uf = UnionFind(10)

    uf.union(1, 2)
    uf.union(2, 3)
    uf.union(4, 5)

    print(f"Find(2): {uf.find(2)}")
    print(f"Find(5): {uf.find(5)}")

    uf.union(3, 4)

    print(f"Find(3): {uf.find(3)}")
    print(f"Find(5): {uf.find(5)}")

コード解説

1. 初期化: __init__メソッドでは、各要素の親を自分自身に設定し、ランクを1に初期化します。

2. Findメソッド: findメソッドは、要素の親を再帰的に探し、パス圧縮を行います。これにより、次回の検索時により早くアクセスできるようになります。

3. Unionメソッド: unionメソッドでは、2つの要素の根を見つけ、ランクに基づいて結合します。ランクが異なる場合は高い方に結合し、同じ場合は一方のランクを増やします。

実行例

上記のコードを実行すると、次のような出力が得られます。

Find(2): 1
Find(5): 5
Find(3): 1
Find(5): 1

この出力は、要素が正しく結合され、Union-Findデータ構造が期待通りに機能していることを示しています。

まとめ

Union by Rankを用いることで、Union-Findデータ構造の性能を大幅に向上させることができます。パス圧縮とランクの管理を組み合わせることで、操作の平均時間計算量はほぼ定数に近づきます。この教材を通じて、Union by Rankの実装を理解し、実際に動かしてみることで、データ構造の効率化の重要性を学ぶことができたでしょう。