Python实现并查集
程序员文章站
2022-03-10 22:44:20
并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。并查集用集合中的某个元素来代表一个集合,该元素称为集合的代表元;一个集合内的所有元素组织成以代表元为根的树形结构。这样,判断两个元素是否属于同一集合,只需判断两个元素的代表元是否相同,合并两个不交集也只需对代表元做更改代表元的操作。 一般来说,一个并查集对应三个操作:初始化+查找根结点函数find+合并集合函数union。初始化字典preprepre:对于每一个元素 xxx,pre[x]pre[x]p...
并查集是一种树型的数据结构,用于处理一些不交集(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