树的应用——使用并查集解决动态连通性问题(含C++代码实现)(中篇:快速合并)_scnu-xyc的博客-程序员宅基地

技术标签: 算法  c++  树结构  算法导论  

上篇:树的应用——使用并查集解决动态连通性问题(含C++代码实现)(上篇:快速查找)

第二种设计:快速合并 Quick-union

在这种设计中,数据结构id[]还是一个整数类型的数组,其索引的含义与之前(上篇:快速查找)相同。但与之前有所不同的是,我们用来表示连通分量,相互连通的对象之间存在双亲与孩子的关系。id[]中存储的值是其索引对应的对象的双亲对象的索引 (值=双亲的索引)。例如:
在这里插入图片描述
对应于id[5]:

index 0 1 2 3 4
value 1 2 2 2 4

“0号对象的双亲是1号,1号对象的双亲是2号,3号对象的双亲是2号。2号和4号对象无双亲(或:双亲是其本身)”
由这种表示法,我们可以得出以下几点规律

1. i i i号对象的双亲是id[ i i i]
2. i i i号对象所在的树的根是id[…id[…id[ i i i]…]…]
3. 相互连通的对象的根相同

接下来我们以上图的情况为例,讲解Union()isConnected()

1.DynamicConnectivity(int N)

与之前(上篇:快速查找)相同。这里我们初始化,得到以下id[]数组:

index 0 1 2 3 4
value 0 1 2 3 4

2.Union(int p,int q):

将p与q连通。根据第2点和第3点规律,我们可以查找p对象所在树的根pRoot和q对象所在树的根qRoot,然后将p对象的根设为q对象的根的孩子,即id[pRoot] = id[qRoot]。例如:
假设目前id[5]为:

index 0 1 2 3 4
value 1 2 2 3 4

即:
在这里插入图片描述
我们执行Union(3,0)。首先我们查找3号对象和0号对象的根,得到3号对象的根为3号,0号对象的根为2号,然后我们将3号对象作为2号对象的孩子节点连上,得到
在这里插入图片描述
反映到id数组上,即为执行id[3]=id[2]

index 0 1 2 3 4
value 1 2 2 2 4

代码实现:
这里,我们需要增加一个成员函数root()用来查找某个对象所在树的根,其函数原型声明为:

int root(int p); //查找并返回返回p号对象的根对象的编号(索引)

实现为:

int DynamicConnectivity::root(int p)
{
    
	while (p != id[p]) p = id[p]; //循环向上搜根
	return p;
}

Union()的实现:

void DynamicConnectivity::Union(int p,int q)
{
    
	//查找p和q的根
	int i = root(p);
	int j = root(q);

	//p的根节点作为孩子连上q的树
	id[i] = id[j];
}

3.isConnected(int p, int q)

根据第3点规律,我们可以知道:如果想知道两个对象是否连通,只需查询其所在树的根结点是否相同即可。
代码实现:

bool DynamicConnectivity::isConnected(int p,int q)
{
    
	return root(p) == root(q);
}

算法分析

本算法最大的时间开销在于root()回溯根,当树很深时,回溯将耗费大量时间。在较一般的情况下,快速合并算法的合并速度会大于快速查找,但在极端情况下,算法整体的效率甚至比快速查找更低(查找消耗的时间会抵消合并的优势甚至把整体弄得更糟)
时间复杂度(在最坏情况下)

算法 初始化函数 DynamicConnectivity(int N) 合并函数 Union(int p,int q) 查找函数 isConnected(int p,int q)
快速查找 Quick-find O(N) O(N) O(N)

因此,本算法依然不适用于节点数巨大的问题。为此,我们将进行改进。
下篇:加权的快速合并

参考:《Algorithms》Bob Sedgewick,Kevin Wayne. Princeton University.

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_51461842/article/details/121192208

智能推荐

0429建立Extended Statistics函数索引问题_weixin_33994444的博客-程序员宅基地

[20160429]建立Extended Statistics 和函数索引问题.txt --11G支持相关数据的统计分析,比如如果两个字段存在相关性通过分析,能够得到更加良好的统计信息,以及生成好的执行计划. --但是如果结合函数索引呢?通过一个简单的例子来说明: --前次做的测试: http://blog.it...

43个功能测试点总结_iteye_15968的博客-程序员宅基地

43个功能测试点总结 软件测试  功能测试就是对产品的各功能进行验证,根据功能测试用例,逐项测试,检查产品是否达到用户要求的功能。针对Web系统的常用测试方法如下:  1. 页面链接检查:每一个链接是否都有对应的页面,并且页面之间切换正确。可以使用一些工具,如LinkBotPro、File-AIDCS、HTML Link Validater、Xenu等工具。LinkBotPro不支持...

UBOOT UART设置(基于mini2440)_羽落飞扬剑舞意的博客-程序员宅基地

基于mini2440的UBOOT UART设置1. 标准9针串口引脚定义根据图3.40的引脚顺序号,如果是作为RS-232C接口,则各引脚定义如表3.2所示。表3.2RS-232C引脚意义表各引脚的电气特性为:在TxD和RxD上,逻辑“1”为-3V~-15V; 逻辑“0”为+3V~+15V。在RTS、CTS、DSR、DTR和DCD等控制线上,信号有效为+3V~+

浅谈MFC类CrackMe中消息处理函数查找方法_weixin_30755709的博客-程序员宅基地

最近一个学姐发给我了一份CrackMe希望我解一下,其中涉及到了MFC的消息函数查找的问题,就顺便以此为例谈一下自己使用的消息函数查找的方法。本人萌新,如果有任何错漏与解释不清的地方,欢迎各路大佬指正。这个CrackMe是一个典型的MFC类型的程序,其框体如下:一、目标以及方法首先我们确认我们的目标是找到两个”注册”按钮的对应消息处理函数,那么有什么手段可以达到我们的目标?在MFC...

android 官方jar,Android 依赖中的jar 包获取方式_全能鬼才木希的博客-程序员宅基地

起因:目前Android 的jar 包我们都是 通过Android studio 的gradle 中添加依赖进行下载。但是eclipse 的用户表示,你在说什么? 读者可能会有疑问,现在还有eclipse 开发Android 的么?有今天我遇到一个有这个需求的朋友。前两个问题还好说,看到第三个,我陷入了沉思,百度不**有得事么。这个人石乐志吧。他说要官方的。我就开始找官方的下载库,没准以后能用上呢...

dir函数:遍历文件名_ainizhongguoaa的博客-程序员宅基地

dir(“地址\”)返回该地址下的第一个文件的文件名Sub t()Dim sr As Stringsr = Dir("G:\社团、活动\JMR\*.xlsx")这里使用了通配符,并指定了文件扩展名;如果不指定,至少应当在地址后加 \ ,以实现遍历DoMsgBox srsr = DirLoop Until sr = ""End Sub使用do

随便推点

获取设备IMEI ,手机名称,系统SDK版本号,系统版本号_weixin_33735077的博客-程序员宅基地

1、获取设备IMEI TelephonyManager tm = (TelephonyManager) getSystemService(Context.TELEPHONY_SERVICE); String IMEIs = tm.getDeviceId() ;需要的权限 <uses-permission androi...

Github配置_Andrew_Zhu的博客-程序员宅基地

-----如果你的代码不知道放哪里好,放到github是一个不错的选择。下面奉上一文入门级别的配置篇。(以下配置同时适用于window和linux) 在github注册完后,首先创建一个仓库(repositry),在你的个人页面右边"Your Repositories"模块,点击 New repository,这里我们把project name 填写

snmp_diexian5592的博客-程序员宅基地

snmpd作为一个服务,本身有系统的一些信息,外部可以通过snmp -get ,walk来获取,而snmptrap理解为一个陷阱,等着掉进来猎物,就是一个收数据的服务,但是收到的数据和snmpd中呈现的数据时互不相关的,两个是独立的,snmptrap收到的数据打到一个日志文件中,通过snmptt可以进行简单的过滤操作,使得拿到的数据更加的符合要求。snmptrap数据收集流程s...

【hihocoder】1515 - 分数调查 (带权并查集)_Dicer_的博客-程序员宅基地

题目链接文章推荐:点击查看用val[x]存放x与根节点的差。感觉带权并查集的find函数跟merge函数有很多递归回溯的思想。 还有大佬说向量偏移之类的,我觉得应该就是利用关系之间的传递性。AC代码:#include <bits/stdc++.h>using namespace std;const int N = 2e5;int n, m, q, x, ...

Servlet_y41992910的博客-程序员宅基地

javax.servlet.Servletpublic interface Servlet {//根据配置初始化,例如在web.xml文件中的写的servlet内容配置信息public void init(ServletConfig config) throws ServletException;//获取配置信息public ServletConfig getServletConfi...

Mac OS利用Composer安装的ThinkPHP遇到404 Not Found The requested URL was not found on this server问题_喜马拉雅的夜空的博客-程序员宅基地

有关Composer安装ThinkPHP的详细过程不再重复,主要针对运行http://localhost/tp5/public/出现404 Not Found The requested URL was not found on this server.的问题,问题如下图所示:解决办法:出现上面这个问题主要是因为ThinkPHP的安装文件与Web服务器的根目录不符,Mac的Apache服务器...