Union-Find (Disjoint Set Union) suit une partition d'éléments en ensembles disjoints et supporte deux opérations quasi-O(1) : find (dans quel ensemble se trouve x ?) et union (fusionner deux ensembles). Il excelle aux requêtes de connectivité.
Chaque ensemble est un arbre avec une racine représentative. Avec et , les opérations s'exécutent en temps quasi-constant (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
Sans path compression et union by rank, les arbres se dégradent en chaînes O(n). Il ne supporte pas la division efficace d'ensembles.
Union-find répond à « ces deux choses sont-elles connectées ? » à grande échelle avec pratiquement aucun coût.
C'est le moteur de Kruskal's MST et de nombreux algorithmes de graphe et de clustering.
Ses deux optimisations offrent une leçon mémorable sur la façon dont de petits trucs structurels donnent des performances quasi-constantes.