Union-Find (Disjoint Set Union), öğelerin ayrık kümeler içinde bölümlenmesini takip eder ve neredeyse O(1) olan iki işlemi destekler: find (x hangi kümede?) ve union (iki kümeyi birleştir). bağlantı sorguları için mükemmeldir.
Her küme, temsili bir köke sahip bir ağaçtır. ve ile işlemler neredeyse sabit zamanda çalışır (inverse Ackermann, α(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
Path compression ve union by rank olmadan, ağaçlar O(n) zincirine bozulur. Kümelerin verimli bölünmesini desteklemez.
Union-find "bu iki şey bağlı mı?" sorusuna muazzam ölçekte neredeyse sıfır maliyetle yanıt verir.
Kruskal MST ve birçok graf ve kümeleme algoritmasının içindeki motorudur.
İki optimizasyonu, küçük yapısal hileler neredeyse sabit-zaman performansını nasıl verir, unutulmaz bir derstir.