不相交集合數據結構保持一組不相交的動態集合S={S1，S2，...,SK},每個集合通過一個代表來識別，代表即集合中的某個成員。
如果x表示一個對象，不相交集合支持以下操作：
MAKE-SET(x):建立一個新的集合，其唯一成員為x。因為各集合是不想交的，故x沒有在其它集合中出現。
UNION(x,y):將包含x和包含y的集合合并為一個新的集合。
FIND-SET(x):返回包含x的集合。
在一個數組中保存每個元素所在集合的名稱。這樣Find操作就是簡單的O(1)查找。要執行Union(x,y)操作，假設x在等價類i中，y在等價類j中，
掃描整個數組，將所有的i變為j。連續N-1次Union操作就要花費Θ(N2)的時間。如果Union操作很多，這個界是不可接受的。
每一個集合用用一個鏈表來表示。鏈表的第一個對象作為它所在集合的代表。鏈表中每個對象都包含一個集合成員，一個指向下一個對象的指針，
以及指向代表的指針。每個鏈表含head和tail指針，head指向鏈表的代表，tail指向鏈表中最后的對象。
Union的簡單實現：將x所在的鏈表拼接到y所在鏈表的表尾。對于原先x所在鏈表中的每一個對象都要更新其指向代表的指針。
平均看來，每個操作需要Θ(N)的時間。
加權合并：每個表含表的長度，總是將更短的表連接到長的表的后面。這樣，m和MAKE-SET,UNION和FIND-SET操作要花費(m+nlgn)的時間。
class SetNode(object): def __init__(self,key): self.key=key self.next=None self.rep=Noneclass SetEntry(object): def __init__(self): self.head=None self.tail=None self.len=0class DisjSet(object): def __init__(self,node): self.setlist=[] def make_set(self,node): S=SetEntry() S.head=node S.tail=node S.len=1 node.rep=node self.setlist.append(S) def find(self,node): return node.rep def union(self,node_x,node_y): rep_x=node_x.rep rep_y=node_y.rep if rep_x!=rep_y: for s in self.setlist: if s.head==rep_x: set_x=s elif s.head==rep_y: set_y=s if set_x.len>=set_y.len: set_x.tail.next=rep_y node=rep_y while node is not None: node.rep=rep_x node=node.next set_x.tail=set_y.tail set_x.len=set_x.len+set_y.len self.setlist.remove(set_y) return rep_x else: set_y.tail.next=rep_x node=rep_x while node is not None: node.rep=rep_y node=node.next set_y.tail=set_x.tail set_y.len+=set_x.len self.setlist.remove(set_x) return rep_y
使用樹來表示一個集合，樹的根用來作為集合的代表。樹的每個節點都含有元素的數據以及一個指向父節點的指針。根節點的指針為空。
可以用數組來非顯式的來表示樹：數組的每個成員T[i]表示元素i的父節點，如果i是根，取p[i]為0或者-1。
如果任意執行Union操作，樹可能會變為退化樹，有幾種方法可以避免這種情況
3.1 靈巧求并算法
總是讓更小的樹成為較大的樹的子樹，稱為按大小求并。另一種方法是按高度求并。
這樣的話，任何節點的深度都不會超過logN，Find操作的運行時間是O(logN),而連續M次操作則花費O(MlogN)。
實現時，讓數組每個元素包含它的樹的大小的負值。
class DisjSet(object): def __init__(self,size): self.list=[-1]*size def find(self,x): if self.list[x]<0: return x else: return self.find(self.list[x]) def union(self,x,y): set_x=self.find(x) set_y=self.find(y) if set_x!=set_y: if self.list[set_x]>self.list[set_y]: self.list[set_y]+=self.list[set_x] self.list[set_x]=set_y return set_y else: self.list[set_x]+=self.list[set_y] self.list[set_y]=set_x return set_x
3.2 路徑壓縮
路徑壓縮在一次Find(X)操作期間執行，從X到根的路徑上的每一個節點都使它的父節點變成根。
路徑壓縮與按大小求并是完全兼容的，而不完全與按高度求并兼容。路徑壓縮時每棵樹的高度會發生變化，可以對每棵樹所存儲的高度估計，用秩rank表示。
class DisjSet_with_rank(object): def __init__(self,size): self.list=[-1]*size def find(self,x): if self.list[x]<0: return x else: self.list[x]=self.find(self.list[x]) return self.list[x] def union(self,x,y): set_x=self.find(x) set_y=self.find(y) if set_x!=set_y: if self.list[set_x]<self.list[set_y]: self.list[set_y]=set_x else: if self.list[set_x]==self.list[set_y]: self.list[set_y]-=1 self.list[set_x]=set_y
路徑壓縮的顯式表示
class SetNode(object): def __init__(self,key): self.parent=None self.key=key self.rank=1def find(node): if node.parent is None: return node else: node.parent=find(node.parent) return node.parentdef union(x,y): x=find(x) y=find(y) if x!=y: if x.rank<=y.rank: if x.rank==y.rank: y.rank+=1 x.parent=y return y else: y.parent=x return x
新聞熱點
疑難解答
