本文主要是介绍[算法入土之路]并查集，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
并查集是一种树型的数据结构，用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
主要操作
初始化
把每个点所在集合初始化为其自身, 并设置连接节点数为1
无论何种实现方式，时间复杂度均为O(N)。
查找
查找元素所在的集合，即根节点。时间复杂度 O(1)
路径压缩
将查找路径上的所有节点的祖先节点位, 置为最终祖先
合并
将两个元素所在的集合合并为一个集合。 时间复杂度 O(1)
判断
判断两个节点是否属于同一个集合。 时间复杂度 O(1)
class DSU:"""并查集 Disjoint Set Union使 union(合并) 和 is_connected(查询) 方法的时间复杂度为 O(1)"""def __init__(self, elems):''':param elems: 元素列表'''self.uf = {i: [i, 1] for i in elems} # key: 元素标识 value: 祖先节点位(如果没有默认为自己) 已经连接的节点数self.sets_count = len(self.uf) # 判断并查集里共有几个集合def find(self, elem):"""查找 elem 的祖先节点:return: elem 祖先节点在 uf 中对应的 value"""r = elemwhile self.uf.get(elem)[0] is not elem:# 如果elem的父节点不是自己 向上查找父节点elem = self.uf.get(elem)[0]# 循环结束 此时 elem 是祖先节点'''路径压缩算法 👇因为并查集目标是找到自己所属的集合 所以每个节点不需要知道自己的间接所属只需要知道自己的最终所属从而最终使得整棵树的横向变宽 减少了查询路径长度'''while r is not elem[0]:# 如果查找到了查找到的祖先节点不是自己 则更改自己的祖先节点位# 向上查询 如果初始elem的父节点的祖先节点位不是最终祖先 则也更改祖先节点位self.uf[r][0], r = elem[0], self.uf[r][0]return self.uf[elem]def union(self, elem_1, elem_2):"""连通 elem_1 和 elem_1:param elem_1: 节点1:param elem_2: 节点2:return:"""# 获取p, q 的祖先节点元素标识 和 祖先节点对应的已经连接的节点数量anc_1, len_1 = self.find(elem_1)anc_2, len_2 = self.find(elem_2)if anc_1 is anc_2:# 如果两个节点的祖先节点相同, 则代表两个节点已经连接了return True# 否则需要想两个集合合并, 将小的合并到大的集合会减少开销 故选择此方式# 判断两个集合哪个更大elif len_1 > len_2:self.uf[anc_2][0] = anc_1 # 将小集合对应的祖先的祖先标识位更改为大集合的祖先节点标识self.uf[anc_1][1] += self.uf[anc_2][1] # 将大集合的长度更改为 大小集合合并之后的大小self.uf[anc_2][1] = 1 # 将小集合祖先的集合长度更改为1else:# 同理self.uf[anc_1][0] = anc_2self.uf[anc_2][1] += self.uf[anc_1][1]self.uf[anc_1][1] = 1self.sets_count -= 1 # 并查集互相隔离的集合数目减一def is_connected(self, elem_1, elem_2):"""判断两节点是否连通:param elem_1: 节点1:param elem_2: 节点2:return: True 两节点相通; False 两节点不通"""return self.find(elem_1)[0] == self.find(elem_2)[0]测试
if __name__ == '__main__':dsu = DSU(["a", "b", "c", "d", "e"])dsu.union("a", "b")dsu.union("a", "e")dsu.union("c", "d")dsu.union("c", "e")print(dsu.is_connected("c", "e"))print(dsu.uf)结果
True
{'a': ['b', 1], 'b': ['b', 5], 'c': ['b', 1], 'd': ['b', 1], 'e': ['b', 1]}这篇关于[算法入土之路]并查集的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
