Union-Find (Disjoint Set Union) traccia una partizione di elementi in insiemi disgiunti e supporta due operazioni quasi-O(1): find (in quale insieme si trova x?) e union (unire due insiemi). Eccelle nelle query di connettività.
Ogni insieme è un albero con una radice rappresentante. Con e , le operazioni vengono eseguite in tempo quasi costante (inverso di 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
Senza path compression e union by rank, gli alberi degradano a catene O(n). Non supporta la divisione efficiente di insiemi.
Union-find risponde a "questi due elementi sono connessi?" su larga scala con costo quasi nullo.
È il motore interno di Kruskal's MST e di molti algoritmi di grafi e clustering.
Le sue due ottimizzazioni rappresentano una lezione memorabile su come piccoli trucchi strutturali producono prestazioni quasi costanti nel tempo.