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

上篇：树的应用——使用并查集解决动态连通性问题（含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$ 号对象的双亲是id[ $i$ ]
2. $i$ 号对象所在的树的根是id[…id[…id[ $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.

本文链接：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