驾校视频网站模板,大同建设局网站,网址地址查询,技术支持 网站建设并查集的优化
在上一节了解到并查集的快速查询#xff0c;合并#xff0c;判断归属组等操作#xff0c;虽然这些操作都非常方便#xff0c;但是在数据量较大的情况下#xff0c;并查集的效率并不算高#xff1a;
上一节中实现代码中使用的合并方法(merge#xff0c;AP…并查集的优化
在上一节了解到并查集的快速查询合并判断归属组等操作虽然这些操作都非常方便但是在数据量较大的情况下并查集的效率并不算高
上一节中实现代码中使用的合并方法(mergeAPI设计中为union)每次合并都需要遍历全部元素的次数而最少要合并N-1次才能将所有元素合并到同一组因此我们要对其合并进行优化
为了提升union算法的性能,我们需要重新设计find方法和merge方法的实现,此时我们先需要对我们的之前数据结构中的groups数组的含义进行重新设定。
使用
优化查询分组which_group方法
我们仍然让groups数组的索引作为结点的元素groups[i]的值不再是当前结点所在的分组标识而是当前结点的父结点根据当前结点的父结点可以找到祖父结点一直往上找直到找到它的根结点根结点则是其真正的分组
Python代码实现及测试
class UF_Tree:def __init__(self, n):self.num_groups nself.groups [i for i in range(n)]def count_groups(self):return self.num_groupsdef in_the_same_group(self, item1, item2):return self.which_group(item1) self.which_group(item2)def which_group(self, item):Find items root------groups[groups[groups[...groups[item]...]]]while self.groups[item] ! item:item self.groups[item]return itemdef merge(self, item1, item2):if self.in_the_same_group(item1, item2):returnself.groups[self.which_group(item1)] self.groups[self.which_group(item2)]self.num_groups - 1if __name__ __main__:UF UF_Tree(5)print(fThe initial number of groups is {UF.num_groups})print(fThe initial number of 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 number of 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
[1, 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
[1, 2, 3, 3, 4]
Input the to-be-merge element: 3
Merge to the target elements group: 4
The number of groups now is 1
[1, 2, 3, 4, 4]
Input the to-be-merge element: 可以寻找到item 0的源分组为4
