为女朋友做网站,产品服务展示型网站有哪些,在线网站推广工具,腾讯网站建设并查集的介绍
并查集#xff08;Union-find#xff09;数据结构也称作合并查找集#xff08;Merge-find set#xff09;或者不相交集数据结构#xff08;disjoint-set data structure#xff09;#xff0c;它是一种记录了由一个或多个元素组成的不连续的分组的集合。并…并查集的介绍
并查集Union-find数据结构也称作合并查找集Merge-find set或者不相交集数据结构disjoint-set data structure它是一种记录了由一个或多个元素组成的不连续的分组的集合。并查集提供常数量的复杂度来添加、合并以及确定两个元素是否属于同一个集合。并查集除了能够实现这些快速便利的操作它在Krukal算法中寻找最小生成树的图也起着关键的作用 并查集结构 并查集是一种树形数据结构但是它和二叉树、红黑树、B树不同它对树形结构的要求十分简单 同一个数据组中的元素对应在同一颗树判断两个元素是否在同一颗树时可以判断根结点是否相同同一数据组中的每一个元素对应树中的一个结点不同数据组之间不存在任何相关的联系可以看做多个数据组成一个森林合并数据组时只需要将一棵树的根结点指向另一颗树的根结点即可树中的结点不存在硬性的顺序/父子关系
并查集的功能实现
方法设计
self.groups 是一个列表其索引代表传入的元素的值其元素代表传入元素所在分组count_groups() 返回并查集中组的数量which_group(item) 判断传入的元素item属于哪一个群组in_the_same_group(item1, item2) 判断传入的两个元素是否在同一个分组merge(item1, item2) 将两个元素各自所在的分组合并到一个组合并后的分组为后者所在的组
Python代码实现
class UnionFind:def __init__(self, n):self.num_groups nself.groups [i for i in range(n)] # Let the indices be the elements, and the elements be the group numbersdef count_groups(self):return self.num_groupsdef which_group(self, item):The indices are items, the elements are group numbersreturn self.groups[item]def in_the_same_group(self, item1, item2):return self.which_group(item1) self.which_group(item2)def merge(self, item1, item2):group1 self.which_group(item1)group2 self.which_group(item2)if group1 group2:returnfor i in range(len(self.groups)):if self.groups[i] group1:self.groups[i] group2self.num_groups - 1代码测试
if __name__ __main__:UF UnionFind(5)print(fThe initial number of groups is {UF.num_groups})print(fThe initial groups is {UF.groups})while True:p int(input(fInput the to-be-merge element: ))q int(input(fMerge to the target elements group: ))if UF.in_the_same_group(p, q):print(fThey are already in the same group)continueUF.merge(p, q)print(fThe number of groups now is {UF.count_groups()})print(UF.groups)测试结果
The initial number of groups is 5
The initial groups is [0, 1, 2, 3, 4]
Input the to-be-merge element: 0
Merge to the target elements group: 1
The number of groups now is 4
[1, 1, 2, 3, 4]
Input the to-be-merge element: 1
Merge to the target elements group: 2
The number of groups now is 3
[2, 2, 2, 3, 4]
Input the to-be-merge element: 2
Merge to the target elements group: 3
The number of groups now is 2
[3, 3, 3, 3, 4]
Input the to-be-merge element: 3
Merge to the target elements group: 4
The number of groups now is 1
[4, 4, 4, 4, 4]
Input the to-be-merge element: 最少需要n-1 4 次合并就可以将所有元素都合并到一个分组到一个组。
