07 — Union-Find (ensembles disjoints)
Ce que tu vas apprendre
- Le problème que résout union-find : regrouper et tester l'appartenance
- L'implémentation par forêt d'arbres
- Les deux optimisations qui donnent un coût quasi constant
- Les usages : composantes connexes, Kruskal, détection de cycle
Prérequis
Union-Find (aussi appelé structure d'ensembles disjoints) répond à une question très précise : « ces deux éléments appartiennent-ils au même groupe ? », avec la possibilité de fusionner des groupes au fil de l'eau. Aucune des structures vues jusqu'ici ne fait ça efficacement. Et la solution est remarquable : avec deux optimisations simples, chaque opération coûte un temps quasi constant, si proche de O(1) que la différence est invisible en pratique.
Le problème
On a n éléments, chacun dans son propre groupe au départ. On veut deux opérations :
- find(x) : à quel groupe appartient
x? (renvoie un représentant du groupe) - union(x, y) : fusionner les groupes de
xety.
Tester si x et y sont dans le même groupe revient à comparer find(x) et find(y). Le défi est de rendre ces deux opérations rapides, alors que les groupes fusionnent dynamiquement.
La forêt d'arbres
L'idée : représenter chaque groupe par un arbre, où chaque élément pointe vers un parent, et la racine est le représentant du groupe. Au départ, chaque élément est sa propre racine (groupe singleton).
pythonclass UnionFind:
def __init__(self, n: int):
self.parent = list(range(n)) # chacun est son propre parent
self.rang = [0] * n
def find(self, x: int) -> int:
while self.parent[x] != x: # remonter jusqu'à la racine
x = self.parent[x]
return x
def union(self, x: int, y: int) -> None:
rx, ry = self.find(x), self.find(y)
if rx == ry:
return # déjà dans le même groupe
self.parent[rx] = ry # rattacher une racine à l'autre
find remonte les parents jusqu'à la racine ; union rattache une racine sous l'autre. Sans optimisation, les arbres peuvent dégénérer en longues chaînes, et find devient O(n). C'est le même piège que le BST. Deux optimisations le corrigent.
Optimisation 1 : l'union par rang
On évite de créer des arbres déséquilibrés en rattachant toujours le plus petit arbre sous la racine du plus grand. On garde une estimation de la hauteur (le « rang ») de chaque racine, et on attache le moins haut sous le plus haut.
python def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry:
return
if self.rang[rx] < self.rang[ry]:
rx, ry = ry, rx # rx est la plus haute racine
self.parent[ry] = rx
if self.rang[rx] == self.rang[ry]:
self.rang[rx] += 1
Cela garde les arbres peu profonds, en O(log n).
Optimisation 2 : la compression de chemin
La seconde optimisation est plus astucieuse. Pendant un find, on en profite pour rattacher directement à la racine tous les nœuds rencontrés sur le chemin. Les find suivants sur ces nœuds seront immédiats.
python def find(self, x):
racine = x
while self.parent[racine] != racine:
racine = self.parent[racine]
while self.parent[x] != racine: # on aplatit le chemin
self.parent[x], x = racine, self.parent[x]
return racine
Chaque find aplatit le chemin parcouru, ce qui accélère tout le reste.
Le résultat : quasi constant
Combinées, l'union par rang et la compression de chemin donnent une complexité étonnante. Chaque opération coûte en moyenne O(α(n)), où α est la fonction inverse d'Ackermann. Cette fonction croît si lentement que pour tout n imaginable dans l'univers, α(n) ≤ 5. Autrement dit, en pratique, chaque opération est en temps constant. C'est l'un des plus beaux résultats de l'analyse de complexité, démontré par Robert Tarjan.
| Opération | Sans optimisation | Avec les deux optimisations |
|---|---|---|
| find | O(n) | O(α(n)) ≈ O(1) |
| union | O(n) | O(α(n)) ≈ O(1) |
Les usages
Union-Find sert dès qu'on raisonne sur des regroupements dynamiques :
- Composantes connexes d'un graphe : tester si deux nœuds sont reliés. On fait l'union de chaque paire d'extrémités d'arête, puis
findrépond à la connexité. C'est central dans la série Graphes à venir. - L'algorithme de Kruskal pour l'arbre couvrant de poids minimal : on ajoute les arêtes par poids croissant, en utilisant union-find pour rejeter celles qui créeraient un cycle.
- Détection de cycle dans un graphe non orienté : si une arête relie deux nœuds déjà dans le même groupe, elle ferme un cycle.
- Regroupement d'éléments équivalents : pixels d'une même région d'image, comptes utilisateurs à fusionner, équivalences à propager.
python# Kruskal : nombre minimal d'arêtes pour relier sans cycle
def compter_groupes(n, aretes):
uf = UnionFind(n)
for a, b in aretes:
uf.union(a, b)
return len({uf.find(i) for i in range(n)}) # nombre de groupes distincts
Conclusion de la série
Cette série a construit les structures dont la série Complexité ne donnait que les coûts, et en a ajouté de spécialisées. Le fil conducteur est constant : chaque structure existe parce qu'un problème rendait les structures généralistes maladroites. Le tas pour servir le prioritaire, le trie pour les préfixes, union-find pour les regroupements. Connaître cette palette, c'est avoir toujours sous la main une structure dont le profil de coûts colle au problème, au lieu de forcer un tableau ou une hashmap là où ils sont mauvais.
La dernière série du parcours algorithmie, les Graphes, s'appuiera directement sur plusieurs de ces structures : la file pour le parcours en largeur, la pile pour la profondeur, la file de priorité pour Dijkstra, et union-find pour la connexité.
Sources
- Tarjan, R. E. (1975). Efficiency of a Good But Not Linear Set Union Algorithm. Journal of the ACM, 22(2). (Analyse en inverse d'Ackermann)
- Galler, B. A., & Fischer, M. J. (1964). An improved equivalence algorithm. Communications of the ACM, 7(5). (Origine de la structure)
- Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.), Chapitre 21 "Data Structures for Disjoint Sets". MIT Press.
- Sedgewick, R., & Wayne, K. (2011). Algorithms (4th ed.), Section 1.5 "Union-Find". Addison-Wesley.