Union-Find (Disjoint Set Union) तत्वों के विभाजन को अलग सेट्स में ट्रैक करता है और दो लगभग-O(1) ऑपरेशन का समर्थन करता है: find (x किस सेट में है?) और union (दो सेट्स को मर्ज करो)। यह कनेक्टिविटी प्रश्नों में बेहतरीन है।
प्रत्येक सेट एक प्रतिनिधि रूट के साथ एक पेड़ है। और के साथ, ऑपरेशन लगभग स्थिर समय में चलते हैं (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) श्रृंखलाओं में गिरावट करते हैं। यह सेट्स के कुशल विभाजन का समर्थन नहीं करता।
Union-Find "क्या ये दोनों चीजें जुड़ी हुई हैं?" का उत्तर विशाल पैमाने पर लगभग बिना किसी लागत के देता है।
यह Kruskal's MST और कई ग्राफ़ और क्लस्टरिंग एल्गोरिदम के अंदर का इंजन है।
इसके दो ऑप्टिमाइजेशन एक यादगार सबक हैं कि कैसे छोटी संरचनात्मक तरकीबें लगभग-स्थिर-समय प्रदर्शन देती हैं।