Union-find

Carte Commune · n° 211858

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.

Lire sur Wikipédia