Union-Find (Disjoint Set Union) παρακολουθεί ένα διαμέρισμα στοιχείων σε disjoint sets και υποστηρίζει δύο σχεδόν O(1) πράξεις: find (σε ποιο set ανήκει το x;) και union (ένωση δύο sets). Διαπρέπει στα ερωτήματα συνδεσιμότητας.
Κάθε set είναι ένα δέντρο με ένα αντιπροσωπευτικό root. Με και , οι πράξεις εκτελούνται σε σχεδόν σταθερό χρόνο (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
Χωρίς path compression και union by rank, τα δέντρα υποβαθμίζονται σε O(n) αλυσίδες. Δεν υποστηρίζει αποτελεσματικό splitting των sets.
Το Union-Find απαντά "είναι αυτά τα δύο πράγματα συνδεδεμένα;" σε μεγάλη κλίμακα με σχεδόν μηδενικό κόστος.
Είναι ο κινητήρας μέσα στο Kruskal's MST και πολλούς αλγόριθμους γραφημάτων και clustering.
Οι δύο βελτιστοποιήσεις του είναι ένα αξιομνημόνευτο μάθημα για το πώς μικρά δομικά κόλπα αποδίδουν σχεδόν σταθερό χρόνο απόδοσης.