Union-Find (Disjoint Set Union) აკვირდება ელემენტების დაყოფას დაკავშირებული ნაკრებებში და მხარს უჭერს ორ თითქმის-O(1) ოპერაციას: find (x რომელ ნაკრებში მდებარეობს?) და union (ორი ნაკრების გაერთიანება). ეს შესანიშნავია კონექტიურობის მოთხოვნებისთვის.
ყველა ნაკრები არის ხე წარმომადგენელი ფესვით. და -ით, ოპერაციები მუშაობენ თითქმის მუდმივი დროით (შებრუნებული აკერმანი, α(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
პути შეკუმშვის და union by rank/size-ის გარეშე, ხეები დეგრადირდება O(n) ჯაჭვებში. ეს არ სჭერს ეფექტიანი ნაკრებების დაყოფა.
Union-find პასუხს აძლევს "ეს ორი რამ დაკავშირებულია?" მასიური მასშტაბით თითქმის არანაირი ღირებულებით.
ეს არის Kruskal's MST-ის და ბევრი გრაფის და კლასტერიზაციის ალგორითმის მოტორი.
მის ორი ოპტიმიზაცია არის ღირსშესანიშნი გაკვეთილი იმის შესახებ, თუ როგორ უძღვება მცირე სტრუქტურული ხრიკებმა თითქმის-მუდმივი დროის პერფორმანსი.