Union-Find (Disjoint Set Union) verwaltet eine Partition von Elementen in disjunkte Mengen und unterstützt zwei nahezu-O(1)-Operationen: find (in welcher Menge ist x?) und union (zwei Mengen zusammenführen). Es zeichnet sich bei Konnektivitäts-Abfragen aus.
Jede Menge ist ein Baum mit einem repräsentativen Wurzelknoten. Mit und laufen Operationen in nahezu konstanter Zeit (inverse Ackermann, α(n)).
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
while self.parent[x] != x:
self.parent[x] = self.parent[self.parent[x]] # compress
x = self.parent[x]
return x
def union(self, a, b):
ra, rb = self.find(a), self.find(b)
if ra == rb:
return False # already connected
if self.rank[ra] < self.rank[rb]:
ra, rb = rb, ra
self.parent[rb] = ra # attach smaller under larger
if self.rank[ra] == self.rank[rb]:
self.rank[ra] += 1
return True
Ohne Pfadkompression und Union by Rank degenerieren Bäume zu O(n)-Ketten. Es unterstützt kein effizientes Aufteilen von Mengen.
Union-Find beantwortet die Frage "sind diese zwei Dinge verbunden?" im großen Maßstab mit nahezu keinen Kosten.
Es ist das Herzstück von Kruskals MST und vielen Graph- und Clustering-Algorithmen.
Its zwei Optimierungen sind eine bemerkenswerte Lektion darüber, wie kleine strukturelle Kniffe nahezu konstante Laufzeit ermöglichen.