Union-Find(素集合データ構造)は要素の分割を互いに素な集合として追跡し、find(xはどの集合に属するか?)とunion(2つの集合をマージ)という2つのほぼO(1)操作をサポートしています。接続性のクエリに優れています。
アイデア
各集合は代表根を持つツリーです。経路圧縮とランク/サイズによる統合により、操作はほぼ定数の償却時間で実行されます(逆アッカーマン、α(n))。
Union-Find(素集合データ構造)は要素の分割を互いに素な集合として追跡し、find(xはどの集合に属するか?)とunion(2つの集合をマージ)という2つのほぼO(1)操作をサポートしています。接続性のクエリに優れています。
各集合は代表根を持つツリーです。経路圧縮とランク/サイズによる統合により、操作はほぼ定数の償却時間で実行されます(逆アッカーマン、α(n))。
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # compress
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller under larger
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
経路圧縮とランク/サイズによる統合がなければ、ツリーはO(n)チェーンに劣化します。集合の効率的な分割はサポートしていません。
Union-Findは「この2つのものは接続されているか?」という質問にほぼコストなしで大規模に答えます。
クラスカルのMST内部のエンジンであり、多くのグラフおよびクラスタリングアルゴリズムのコア部分です。
その2つの最適化は、小さな構造的なトリックがいかにして準定時間のパフォーマンスをもたらすかを示す印象的な教訓です。