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 અને ઘણામાં આલેખ અને ક્લસ્ટરીંગ અલ્ગોરિધમમાં મોટર છે.
તેના બે ઑપ્ટિમાઇઝેશન્સ એક સ્મરણીય પાઠ છે કે કેવી રીતે નાની માળખાકીય યુક્તિઓ લગભગ-સ્થિર-સમય કામગીરી આપે છે.