Union-find

Étant donné un ensemble d'éléments, il est souvent utile de le partitionner en un certain nombre de classes disjointes, c'est-à-dire de représenter une relation d'équivalence. Une structure de données pour le problème des classes disjointes maintient une telle partition et comme elle a essentiellement deux opérations trouver et unir , on l'appelle union-find, suivant en cela la terminologie anglaise:

• Find (trouver): détermine la classe d'équivalence d'un élément; elle sert aussi à déterminer si deux éléments appartiennent à la même classe d'équivalence.
• Union (unir): réunit deux classes d'équivalence en une seule.

Une autre opération importante, MakeSet, construit une classe d'équivalence contenant un seul élément, autrement dit un singleton.

Afin de définir ces opérations plus précisément, il faut choisir un moyen de représenter les classes. L'approche traditionnelle consiste à sélectionner un élément particulier de chaque classe, appelé le représentant, pour identfier la classe entière. Lors d'un appel, Find(x) retourne le représentant de la classe de x.

Sommaire 1 Solution utilisant des listes chaînées 2 Solution utilisant des forêts 3 Applications 4 Voir aussi 5 Notes et références de l'article

Solution utilisant des listes chaînées

La solution la plus immédiate pour le problème des classes disjointes consiste à construire une liste chaînée pour chaque classe. On choisit alors l'élément en tête de liste comme représentant.

MakeSet crée une liste contenant un élément. Union concatène les deux listes, une opération en temps constant. Malheureusement, l'opération Find nécessite alors un temps Ω(n) avec cette approche.

On peut y remédier en ajoutant à chaque élément d'une liste chaînée un pointeur vers la tête de la liste ; Find est alors réalisée en temps constant. Cependant, on a détérioré l'efficacité de Union, qui doit maintenant parcourir tous les éléments d'une des deux listes pour les faire pointer vers la tête de l'autre liste, ce qui nécessite un temps Ω(n).

On peut améliorer ceci en ajoutant toujours la plus petite des deux listes en queue de la plus longue, ce qui porte le nom d' heuristique de l'union pondérée. Ceci nécessite de maintenir la longueur des listes au fur et à mesure des opérations. Avec cette solution, une séquence de m opérations MakeSet, Union et Find sur n éléments nécessite un temps O(m + nlog n). Pour obtenir de meilleurs résultats, nous devons considérer une structure de données différente.

Solution utilisant des forêts

On considère maintenant une structure de données dans laquelle chaque classe est représentée par un arbre dans lequel chaque nœud contient une référence vers son nœud père. Une telle structure de forêt a été introduite par Bernard A. Galler et Michael J. Fisher en 1964^[1], bien que son analyse détaillée ait attendu plusieurs années.

Dans une telle forêt, le représentant de chaque classe est la racine de l'arbre correspondant. Find se contente de suivre les liens vers les nœuds pères jusqu'à atteindre la racine. Union réunit deux arbres en attachant la racine de l'un à la racine de l'autre. Une manière d'écrire ces opérations est la suivante :

 function MakeSet(x)
     x.parent := null
 
 function Find(x)
     if x.parent == null
        return x
        
     return Find(x.parent)
 
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     xRoot.parent := yRoot

Sous cette forme naïve, cette approche n'est pas meilleure que celle des listes chaînées, car les arbres créés peuvent être très déséquilibrés. Mais elle peut être améliorée de deux façons.

La première consiste à toujours attacher l'arbre le plus petit à la racine de l'arbre le plus grand, plutôt que l'inverse. Pour évaluer quel arbre est le plus grand, on utilise une heuristique appelée le niveau : les arbres contenant un élément sont de niveau zéro, et lorsque deux arbres de même niveau sont réunis, le résultat a un niveau plus grand d'une unité. Avec cette seule amélioration, la complexité amortie des opérations MakeSet, Union et Find devient O(logn). Voici les nouveaux codes de MakeSet et Union :

 function MakeSet(x)
     x.parent := null
     x.rank   := 0
 
 function Union(x, y)
     xRoot = Find(x)
     yRoot = Find(y)
     if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot != yRoot
         yRoot.parent := xRoot
         xRoot.rank := xRoot.rank + 1

La seconde amélioration, appelée compression de chemin, consiste à aplatir la structure d'arbre à chaque fois que l'on utilise Find. L'idée est que chaque nœud rencontré sur le chemin menant à la racine peut être directement relié à la racine; tous ses nœuds ont en effet le même représentant. Pour réaliser ceci, on fait un parcours en direction de la racine de l'arbre, afin de la déterminer, puis un autre parcours pour faire de cette racine le parent immédiat de tous les nœuds rencontrés en chemin. L'arbre résultant est aplati, ce qui améliore les performances de futurs accès à ces nœuds, mais aussi à d'autres nœuds pointant vers ceux-ci, directement ou indirectement. Voici l'opération Find améliorée :

 function Find(x)
     if x.parent == null
        return x
  
     x.parent = Find(x.parent)
     return x.parent

Ces deux améliorations sont complémentaires. Conjointement, elles permettent d'atteindre une complexité amortie en temps O(α(n)), où α(n) est la réciproque de la fonction f(n) = A(n,n) et A la fonction d'Ackermann dont la croissance est extrêmement rapide. α(n) vaut moins de 5 pour toute valeur n en pratique^[2]. En conséquence, la complexité amortie par opération est de fait une constante.

Il n'est pas possible d'obtenir un meilleur résultat : Fredman et Saks ont montré en 1989 que Ω(α(n)) mots en moyenne doivent être lus par opération sur toute structure de données pour le problème des classes disjointes.

Applications

Cette structure est souvent utilisée pour identifier les composantes connexes d'un graphe. Elle est également utilisée dans l'algorithme de Kruskal, pour trouver l'arbre couvrant de poids minimal d'un graphe.

Voir aussi

• find: une commande UNIX.

Notes et références de l'article

• Zvi Galil et Giuseppe F. Italiano, « Data structures and algorithms for disjoint set union problems », septembre 1991, ACM Digital Library, p. Volume 23, Issue 3, pages 319-344. Consulté le 27 octobre 2007
• J. A. Spirko and A. P. Hickman, « Molecular-dynamics simulations of collisions of Ne with La@C₈₂ », mai 1998, p. Phys. Rev. A 57, 3674–3682. Consulté le 27 octobre 2007