Publié · en amélioration
Algorithm
Union-Find (ensembles disjoints) range des éléments en groupes sans chevauchement et fusionne des groupes ou teste l'appartenance en temps quasi constant.
Union-Find, aussi appelée structure d'ensembles disjoints, gère une collection d'éléments répartis en ensembles qui ne se chevauchent pas. Elle n'offre que deux opérations : find renvoie le représentant de l'ensemble auquel appartient un élément, et union fusionne les ensembles de deux éléments. Chaque ensemble est stocké comme un arbre de pointeurs vers le parent, dont la racine est le représentant.
Lorsque les connexions ne font que s'ajouter et qu'il faut demander sans cesse si deux éléments sont reliés, Union-Find est bien plus rapide qu'un parcours du graphe à chaque fois. Avec la compression de chemin et l'union par rang ou par taille, le coût amorti par opération tombe à la fonction d'Ackermann inverse α(n), qui ne dépasse pas 4 pour toute entrée réaliste. C'est l'outil de base de l'arbre couvrant minimal de Kruskal, de la détection de cycles, des composantes connexes et des problèmes de regroupement comme la fusion de comptes, et un sujet fréquent en entretien technique.
Commencez par implémenter find et union sur un seul tableau parent, puis suivez à la main comment un arbre dégénère en chaîne sans optimisation. Ajoutez ensuite l'union par taille et la compression de chemin l'une après l'autre en observant l'évolution de la profondeur des arbres. Enfin, résolvez des problèmes de composantes connexes, de détection de cycles et de Kruskal pour prendre l'habitude d'exploiter la valeur de retour de union.
find remonte les pointeurs vers le parent jusqu'à la racine, le représentant, et union accroche une racine sous l'autre pour fusionner deux ensembles.
find rattache directement à la racine les nœuds visités et aplatit l'arbre, ce qui accélère les appels suivants.
Accrocher le plus petit arbre sous le plus grand limite la hauteur de chaque arbre à log n.
Avec les deux optimisations, m opérations coûtent O(m α(n)), et la fonction d'Ackermann inverse α(n) vaut au plus 4 en pratique.
La classe DSU stocke les ensembles dans deux tableaux, parent et size. find remonte les pointeurs et applique la réduction de chemin de moitié, en reliant chaque nœud à son grand-parent, pour garder des arbres plats. union accroche le plus petit ensemble sous le plus grand et renvoie False si les deux éléments sont déjà dans le même ensemble. L'exemple regroupe six éléments en trois ensembles puis affiche des tests d'appartenance et le nombre d'ensembles.
union_find.py
class DSU:
def __init__(self, n):
self.parent = list(range(n))
self.size = [1] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # path halving
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False
if self.size[ra] < self.size[rb]:
ra, rb = rb, ra
self.parent[rb] = ra
self.size[ra] += self.size[rb]
return True
dsu = DSU(6)
for a, b in [(0, 1), (1, 2), (3, 4)]:
dsu.union(a, b)
print(dsu.find(2) == dsu.find(0)) # True
print(dsu.find(4) == dsu.find(5)) # False
print(len({dsu.find(x) for x in range(6)})) # 3
python union_find.pySix chapitres pour aller de l'installation aux notions essentielles de Union-Find.
Posez vos questions, partagez votre expérience et échangez vos avis sur Union-Find.
Aucune discussion pour l'instant. Lancez la première.
0 commentaire
Se connecter · Connectez-vous pour laisser un commentaire.
Soyez le premier à commenter.