Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Union-find
Résumé
thumb|Partition avec 8 classes (qui sont des singletons) obtenue avec MakeSet(1), ..., MakeSet(8).|255x255px
thumb|Partition avec 3 classes disjointes obtenue après Union(1, 2), Union(3, 4), Union(2, 5), Union(1, 6) et Union(2, 8).|255x255px
En informatique, union-find est une structure de données qui représente une partition d'un ensemble fini (ou de manière équivalente une relation d'équivalence).
Elle a essentiellement deux opérations trouver et unir et est appelée union-find, suivant en cela la terminologie anglo-saxonne :
Find (trouver) : détermine la classe d'équivalence d'un élément ; elle sert ainsi à 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.
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 (le représentant étant la tête de la liste). 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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.