Union-Find (Disjoint Set Union) houdt een partitie van elementen in disjuncte verzamelingen bij en ondersteunt twee bijna-O(1) operaties: find (in welke verzameling zit x?) en union (voeg twee verzamelingen samen). Het blinkt uit bij connectiviteitsvragen.
Elke verzameling is een boom met een representatieve wortel. Met en draaien operaties in bijna constante tijd (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
Zonder padcompressie en union by rank degraderen bomen tot O(n) ketens. Het ondersteunt geen efficiënt splitsen van verzamelingen.
Union-find beantwoordt "zijn deze twee dingen verbonden?" op massale schaal met bijna geen kosten.
Het is de motor in Kruskal's MST en veel graaf- en clusteringalgoritmen.
Zijn twee optimalisaties zijn een memorabele les in hoe kleine structurele trucs bijna-constante-tijd prestaties opleveren.