Union-Find

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

É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 identifier la classe entière. Lors d'un appel, Find(x) retourne le représentant de la classe de x.

Solution utilisant des listes chaînées[modifier | modifier le code]

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[modifier | modifier le code]

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(\log n). Voici les nouveaux codes de MakeSet et Union :

 function MakeSet(x)
     x.parent := x
     x.rank   := 0
 
 function Union(x, y)
     xRoot := Find(x)
     yRoot := Find(y)
     if xRoot == yRoot
         return
     if xRoot.rank < yRoot.rank
         xRoot.parent := yRoot
     else if xRoot.rank > yRoot.rank
         yRoot.parent := xRoot
     else
         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 != 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(\alpha(n)), où \alpha(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. \alpha(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 \Omega(\alpha(n)) mots en moyenne doivent être lus par opération sur toute structure de données pour le problème des classes disjointes.

Applications[modifier | modifier le code]

Cette structure est souvent utilisée pour identifier les composantes connexes d'un graphe (voir l'article Algorithmes de connexité basés sur des pointeurs). Elle est également utilisée dans l'algorithme de Kruskal, pour trouver l'arbre couvrant de poids minimal d'un graphe.

Voir aussi[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

  • L'opération Union en théorie des ensembles
  • find, une commande UNIX

Lien externe[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. Bernard A. Galler et Michael J. Fisher, « An improved equivalence algorithm, [[Communications of the ACM]] », ACM Digital Library,‎ mai 1964 (consulté le 27 octobre 2007), p. Volume 7, Issue 5, pages 301-303
  2. (en) Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest et Clifford Stein, Introduction to Algorithms, MIT Press et McGraw-Hill,‎ 2001, 2e éd. [détail de l’édition] (ISBN 0-262-03293-7, 978-0-262-03293-3 et 978-0-262-53196-2). Chapter 21: Data structures for Disjoint Sets, pp.498–524.

Sources[modifier | modifier le code]