Union-Find (Ensembles Disjoints) expliqué, avec du Code

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

Qu'est-ce qu'Union-Find ?

Union-find, aussi appelé disjoint set union (DSU), est une structure de données qui suit un ensemble d'éléments répartis en groupes disjoints. Chaque élément appartient à exactement un groupe, et chaque groupe est identifié par un unique représentant, sa racine.

L'astuce tient à la façon dont les groupes sont stockés : comme une forêt d'arbres. Chaque élément détient un pointeur vers son parent, et remonter les parents mène toujours à la racine du groupe. Deux éléments sont dans le même groupe si et seulement s'ils partagent la même racine. C'est toute l'idée, et tout le reste consiste à la rendre rapide.

Les Deux Opérations

Union-find ne propose que deux opérations, et toute sa réputation repose sur le fait de les faire toutes deux presque instantanément.

• find(x) renvoie la racine du groupe contenant x, en remontant les pointeurs de parent. Deux éléments sont connectés lorsque find(a) == find(b).
• union(a, b) fusionne les deux groupes en faisant d'une racine le parent de l'autre.

Comme les groupes ne font que fusionner et ne se scindent jamais, union-find est parfait pour les problèmes où les connexions s'ajoutent au fil du temps mais ne sont jamais retirées.

La Version Naïve et Son Problème

Une première tentative se contente de stocker des pointeurs de parent et fusionne en pointant une racine vers l'autre. Ça marche, mais il y a un vilain écueil : rien n'empêche les arbres de devenir de longues chaînes. Si chaque union empile un nœud sur le précédent, find doit parcourir une chaîne de longueur n, et chaque opération se dégrade en O(n).

Ce n'est pas mieux qu'une simple liste. La solution tient en deux petites modifications qui, ensemble, comptent parmi les résultats les plus célèbres des structures de données.

Deux Optimisations Qui Changent Tout

L'union par rang garde les arbres peu profonds. En fusionnant deux groupes, accrochez toujours l'arbre le plus court sous la racine du plus haut. Un arbre court suspendu à un grand n'augmente pas la hauteur, si bien que les arbres restent plats.

La compression de chemin aplatit au passage. Chaque fois que find remonte jusqu'à une racine, il repointe chaque nœud traversé directement vers cette racine. Le prochain find sur l'un d'eux n'est alors qu'un seul saut. La figure ci-dessous montre un find qui effondre une chaîne.

Utilisées ensemble, l'union par rang et la compression de chemin gardent chaque arbre presque totalement plat, de sorte que les deux opérations s'exécutent en temps quasi constant. Chacune seule aide ; c'est leur combinaison qui rend union-find célèbre.

Implémentation en Python

Toute la structure tient dans une petite classe. Deux tableaux font tout le travail : parent et rank.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # chaque élément commence comme sa propre racine
        self.rank = [0] * n            # une borne supérieure sur la hauteur de chaque arbre

    def find(self, x):
        # Compression de chemin : pointer x directement vers la racine.
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # déjà dans le même groupe

        # Union par rang : accrocher l'arbre le plus court sous le plus haut.
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True

Remarquez que union renvoie False lorsque les deux éléments étaient déjà connectés. Ce seul booléen est ce qui rend la détection de cycles et l'algorithme de Kruskal si nets : si une union échoue, l'arête que vous alliez ajouter aurait fermé un cycle.

Complexité : Presque Constante

Avec les deux optimisations, une suite de m opérations sur n éléments s'exécute en O(m · α(n)) au total, où α est la fonction d'Ackermann inverse.

La fonction d'Ackermann inverse croît si lentement que α(n) vaut au plus 4 pour tout n qui tiendrait dans l'univers observable. En pratique, traitez chaque opération comme du temps constant. Pour voir comment cela se situe parmi tous les algorithmes de graphes, voir le guide de complexité et l'aide-mémoire.

Où l'Utilise-t-on

Union-find apparaît partout où l'on doit suivre la connexité à mesure qu'elle grandit.

• Arbre couvrant minimal de Kruskal : triez les arêtes, puis ajoutez chacune seulement si ses extrémités sont dans des groupes différents. Union-find est le test de cycle. Voir arbres couvrants minimaux.
• Détection de cycles dans un graphe non orienté : pour chaque arête, si les deux extrémités partagent déjà une racine, l'arête ferme un cycle.
• Composantes connexes : unissez chaque arête, puis comptez les racines distinctes.
• Connexité dynamique et entretiens : des problèmes comme Number of Provinces, Redundant Connection et Accounts Merge sont tous de l'union-find déguisé. Voir les algorithmes de graphes pour les entretiens de code.

Il se trouve aussi à l'étape 3 de la feuille de route de la théorie des graphes, juste là où vous apprenez les arbres couvrants.