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 आणि अनेक आलेख आणि क्लस्टरिंग अल्गोरिदमचे इंजिन आहे.
त्याचे दोन अनुकूलन हे लहान संरचनात्मक युक्त्यांनी जवळजवळ-स्थिर-वेळ कार्यक्षमता कसे मिळू शकते याचा एक स्मरणीय पाठ आहे.