我要评论并查集是一种树型的数据结构，用于处理一些不交集（Disjoint Sets）的合并及查询问题。并查集用集合中的某个元素来代表一个集合，该元素称为集合的代表元；一个集合内的所有元素组织成以代表元为根的树形结构。这样，判断两个元素是否属于同一集合，只需判断两个元素的代表元是否相同，合并两个不交集也只需对代表元做更改代表元的操作。
初始化
- 字典：对于每一个元素 ，为在树形结构上的父节点，如果是根节点，则令；
- 字典：为元素在当前树结构中的高度（由下至上）；
- 整数：并查集中集合的个数。
查找函数find
- 对于查找操作，假设需要确定所在的的集合，也就是确定集合的代表元，可以沿着不断在树形结构中向上移动，直到到达根节点。
- 路径压缩：为了加快查找速度，在查找根结点的过程中，顺便把子结点的父结点改成根结点。
合并集合函数union
- 合并两个集合后，并查集中集合个数减1。
class UnionFindSet(object):
def __init__(self, data_list):
self.parent = {}
self.rank = {}
self.sets_count=len(data_list) # 判断并查集里共有几个集合, 初始化默认互相独立
for d in data_list:
self.parent[d] = d # 初始化节点的父节点为自身
self.rank[d] = 1 # 初始化rank为1
def find(self, d):
"""使用递归的方式来查找根节点
路径压缩：在查找父节点的时候，顺便把当前节点移动到父节点下面
"""
father = self.parent[d]
if(d != father):
father = self.find(father)
self.parent[d] = father
return father
def is_same_set(self, a,b):
"""查看两个节点是不是在一个集合里面"""
return self.find(a) == self.find(b)
def union(self, a, b):
"""将两个集合合并在一起"""
if not a or not b:return
a_head = self.find(a)
b_head = self.find(b)
if(a_head != b_head):
a_rank = self.rank[a_head]
b_rank = self.rank[b_head]
if a_rank >= b_rank:
self.parent[b_head] = a_head
if a_rank==b_rank:
self.rank[a_rank]+=1
else:
self.parent[a_head] = b_head
self.sets_count-=1
if __name__ == '__main__':
a = [1,2,3,4,5]
ufs = UnionFindSet(a)
ufs.union(1,2)
ufs.union(3,5)
ufs.union(3,1)
print(ufs.sets_count)
print(ufs.is_same_set(2,5)) # True
print(ufs.parent)
print(ufs.rank)
输出：
2
True
{1: 1, 2: 1, 3: 1, 4: 4, 5: 1}
{1: 3, 2: 1, 3: 1, 4: 1, 5: 1}
并查集用途：
- 维护无向图的连通性。支持判断两个点是否在同一连通块内，和判断增加一条边是否会产生环。
- 用在求解最小生成树的Kruskal算法里。
本文地址：https://blog.csdn.net/Hanx09/article/details/107235923
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论