Union-Find (Disjoint Set Union) a thracann an roinn d'eilimintí i shraitheanna scartha agus tacaíonn sé dhá oibríocht beagnach-O(1): find (cén tsraith a bhfuil x ann?) agus union (dhá shraith a shuimiú). Tá sé den scéal is fearr ar ghealadh nascacht.
Is crann an gach sraith le fréamh ionadaíoch. Le agus , ritheann oibríochtaí in am beagnach-seasmhach (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
Gan path compression agus union by rank, meathlaonn crainn go slabhra O(n). Ní thacaíonn sé le roinnt éifeachtach sraitheanna.
Freagraíonn Union-Find "an bhfuil an dá rud seo nasctha?" ar scála ollmhór gan gur ghá aon chostas.
Is é an t-inneall taobh istigh de Kruskal's MST agus go leor halgartam graf agus clúsúchán.
Airítear a dhá bharbhéas ar an gcóir go mbunú conas a thugann cleasanna beag struchtúrtha feidhmíochta beagnach-seasmhach.