Union-Find

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

Sommaire

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(log n). 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 (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

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

Notes et références de l'article

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

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Union-Find de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • 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… …   Wikipédia en Français

  • Union-Find — Eine Union Find Datenstruktur verwaltet die Partition einer Menge. Der abstrakte Datentyp wird durch die Menge der drei Operationen {Union, Find, Make Set} gebildet. Union Find Strukturen dienen zur Verwaltung von Zerlegungen in disjunkten Mengen …   Deutsch Wikipedia

  • Union-Find-Struktur — Eine Union Find Datenstruktur verwaltet die Partition einer Menge. Der abstrakte Datentyp wird durch die Menge der drei Operationen {Union, Find, Make Set} gebildet. Union Find Strukturen dienen zur Verwaltung von Zerlegungen in disjunkte Mengen …   Deutsch Wikipedia

  • Find — est une commande UNIX permettant de chercher des fichiers dans un ou plusieurs répertoires selon des critères définis par l utilisateur. Par défaut, find retourne tous les fichiers contenus dans l arborescence du répertoire courant. find permet… …   Wikipédia en Français

  • find — est une commande UNIX permettant de chercher des fichiers dans un ou plusieurs répertoires selon des critères définis par l utilisateur. Par défaut, find retourne tous les fichiers contenus dans l arborescence du répertoire courant. find permet… …   Wikipédia en Français

  • Union-By-Size — Eine Union Find Datenstruktur verwaltet die Partition einer Menge. Der abstrakte Datentyp wird durch die Menge der drei Operationen {Union, Find, Make Set} gebildet. Union Find Strukturen dienen zur Verwaltung von Zerlegungen in disjunkten Mengen …   Deutsch Wikipedia

  • Union of Christendom — • Includes the Catholic Church together with the many other religious communions which have either directly or indirectly, separated from it Catholic Encyclopedia. Kevin Knight. 2006. Union of Christendom     Union of Christend …   Catholic encyclopedia

  • Union busting — is a practice that is undertaken by an employer or their agents to prevent employees from joining a labor union, or to disempower, subvert, or destroy unions that already exist.During contract negotiations, established unions may declare a strike …   Wikipedia

  • Union Cemetery — is the name of hundreds [ [http://www.findagrave.com/cgi bin/fg.cgi?page=csr CScn=Union+Cemetery CScntry=4 CSst=0 List of Cemeteries named Union Cemetery in the United States] from Find A Grave] of cemeteries in the United States, including: *… …   Wikipedia

  • Union blockade — Part of the American Civil War An 1861 cartoon map of the blockade, known as Winfield Scott …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”