复杂数据结构-并查集
复杂数据结构-并查集
支持两个操作:
(1)查询两个元素是否属于一个集合isSameSet(A,B)
(2)合并两个集合union(A,B)(先查询,再合并)
目的:
减少查询和合并时间复杂度
结构:
(value,parent)
单个元素集合,指针指向自己
具体操作:
(1)查询:一直往上找,找到上级指针指回自己的点,即该集合的代表点。如果代表点相同,在一个集合;否则属于不同的集合。
(2)合并:较少节点的集合挂在较大节点集合的下面。
注:往上查询的过程中,将整个链打平,降低下次查询的代价(重要特性)
代码实现:
(1)fatherMap(节点和父亲节点)
(key:节点,value:父节点)
(2)sizeMap(代表节点和该集合大小)
(key:代表节点,value:结合大小)【若不是代表节点,该值无效】
class UnionFindSet():
def __init__(self):
self.fatherMap = {}
self.sizeMap = {}
def makesets(self,nodes): #初始化fatherMap和sizeMap
self.fatherMap.clear()
self.sizeMap.clear()
for node in nodes:
self.fatherMap[node] = node
self.sizeMap[node] = 1
return self.fatherMap, self.sizeMap
def findhead(self,node): #寻找代表节点
father=self.fatherMap[node]
if father!=node:
father=self.findhead(father)
self.fatherMap[node]=father
return father
def isSameSet(self,a,b): #判断是否在同一集合中
return self.findhead(a)==self.findhead(b)
def union(self,a,b): #合并两个集合
if a==None or b==None:
return
ahead=self.findhead(a)
bhead=self.findhead(b)
if ahead!=bhead: #判断是否在同一集合中
aSetsize=self.sizeMap[ahead]
bSetsize=self.sizeMap[bhead]
if aSetsize<bSetsize: #将小的集合挂在大的集合下面,更新两个map
self.fatherMap[ahead]=bhead
self.sizeMap[bhead]=aSetsize+bSetsize
else:
self.fatherMap[bhead] = ahead
self.sizeMap[ahead] = aSetsize + bSetsize
return self.fatherMap,self.sizeMap
mm=UnionFindSet()
print(mm.makesets([3,4,2,6,7]))#初始化
print(mm.findhead(6)) #寻找代表节点
print(mm.isSameSet(4,3))
print(mm.union(3,4)) #合并
print(mm.isSameSet(4,3)) #是否在一个集合中
复杂度:
假设元素个数为N
若查询的次数+合并的次数>N
则单次查询和单次合并"平均时间复杂度"O(1)