并查集算法篇上期：并查集原理及实现

news/2025/2/22 18:50:42

cle class="baidu_pl">

cle_content" class="article_content clearfix">

content_views" class="markdown_views prism-atom-one-dark">

c="https://i-blog.csdnimg.cn/direct/539bf26104bd42cf87dce34fc1ac56a2.png" alt="在这里插入图片描述" />

引入

那么我们在介绍我们并查集的原理之前࿰c;我们先来看一下并查集所应用的一个场景：那么现在我们有一个长度为n的数组࿰c;他们分别属于不同的集合࿰c;那么现在我们要查询数组当中某个元素和其他元素是否处于同一集合当中࿰c;或者我们想把它们合并到同一个集合当中࿰c;以及查询该集合的数量࿰c;那么这些都可以交给我们的并查集来进行实现。

那么我们数组中处于相同的集合的元素的位置是离散的࿰c;那么很多人看到并查集所应用的场景࿰c;那么常规思路实现我们的并查集一般会想到就是采取我们的哈希表这个class="tags" href="/tags/ShuJuJieGou.html" title=数据结构>数据结构࿰c;对于每一个集合我们建立一张哈希表࿰c;如果我们查询这两个元素是否在同一个集合当中࿰c;那么我们就是确定他们是否在同一张表当中࿰c;那么就会遍历我们这张哈希表࿰c;如果要合并两个不同的集合࿰c;那么我们就该另一张哈希表中的元素全部添加进该哈希表当中࿰c;我们哈希表实现我们的并查集是肯定没有问题的࿰c;但是我们有更为简单并且高效的实现方式࿰c;那么就是通过我们的数组来实现

并查集原理

那么我们首先我们知道我们判断两个元素所处的集合是否是一个集合࿰c;那么我们的集合肯定得有一个标识符来进行区分࿰c;那么这里我们区分不同的集合的话࿰c;我们就是选取该集合当中的一个代表元素的索引或者编号来作为该集合的一个标识符。

那么我们会首先准备一个father数组和一个size数组(其中size数组可有可不有）࿰c;那么我们的father数组的每一个位置就对应我们原始数组当中的每一个位置࿰c;那么其中father数组的作用就是确定数组每一个位置在集合当中的直接后继的节点编号是谁࿰c;那么想你可能看不懂我刚才的那句话࿰c;但是没关系࿰c;我在下文会进行讲解。
那么我们首先初始化我们的并查集的时候࿰c;我们将我们该数组中的每个元素自己作为一个集合࿰c;那么该集合的代表元素就是他们本身

那么我们如何理解我们这个集合呢࿰c;那么我们对于每一个集合来说࿰c;那么处于该集合当中的元素就是以一个树的形式来进行组织的࿰c;那么我们该树的根节点就是该集合的代表元素࿰c;这个树不是说我们的并查集的集合的实现就是按照真的class="tags" href="/tags/ShuJuJieGou.html" title=数据结构>数据结构当中的树那样用指针进行构造࿰c;而是说我们的处于同一集合当中的元素可以形象理解为他们是以一个树的形式来组织࿰c;就像我们理解DFS的递归过程就形象的理解为类似于一棵多叉树的遍历。

那么最开始我们初始化并查集的时候࿰c;假设我们现在有一个长度为n的数组࿰c;那么我们先让该数组当中的每一个元素自己作为一个集合࿰c;那么我们就可以理解为每个集合当中所对应对应的树的节点就只有一个就是当前数组每个元素它本身࿰c;那么它的下一个直接后继节点就是它自己。

那么我们该数组中任意两个位置所处的集合要进行合并的话࿰c;那么我们就首先判断他们是否处于同一个集合࿰c;如果处于同一个集合࿰c;就没有必要进行合并࿰c;如果不处于同一个集合的话࿰c;那么我们就可以合并࿰c;那么刚开始我们每一个集合都只有当前数组每一个位置本身的一个元素࿰c;那么我们合并的话࿰c;我们就将我们这个其中一个集合所对应的树的根结点原本就是自己本身࿰c;并且它的指向后继节点的指针是指向自己࿰c;那么我们就该根结点的指针给指向另一个元素所处集合所对应树的根结点࿰c;那么我们实现这个过程的话࿰c;我们知道我们father数组记录的是数组当中每一个位置它的父节点的索引编号࿰c;那么最开始由于我们每一个元素自己作为一个集合࿰c;那么father数组当中的每一个位置的记录的父节点的编号就是他们本身
例：father[0]=0,father[1]=1,father[2]=2…

那么如果此时我们假设数组下标为0的元素与数组下标为1的元素合并了࿰c;那么我们就在father数组当中下标为0的位置处原本记录的编号就是0࿰c;那么我们将其修改为1࿰c;那么此时这步操作我们就可以理解为我们一个集合对应的树的根节点的指针原本的指向是自己࿰c;而现在我们在该集合所对应的树插入到另一个集合所对应的树当中作为一个子树了࿰c;而我们该集合的根节点原本的指向是自己࿰c;现在我们将其修改指向为另一个要合并集合对应的树的根节点࿰c;所以此时该树的根节点不再是原先集合的根节点了࿰c;而是另一个我们插入的集合原本的根节点࿰c;所以现在两个集合的根节点相同࿰c;那么两个集合就是同一个集合了࿰c;从而实现合并。

那么接下来我们每次合并两个数组中任意两个数所处的集合࿰c;我们都要先查找两个数所处的集合的代表元素的编号࿰c;看他们是否相同࿰c;而现在假设这个数组中的每个集合已经经过多次的合并࿰c;那么意味着该元素所处的树上的节点可能不只有之前初始化时它自己一个了࿰c;那么我们就得往上找到该元素所处的树的根结点࿰c;那么我们知道father数组记录的是数组中每一个位置的元素在树当中的直接后继࿰c;也就是它的父节点࿰c;那么接下来我们就需要遍历我们的father数组࿰c;假设我们现在要找下标为0的元素所处集合的根结点也就是代表元素࿰c;那么我们就遍历father数组࿰c;那么我们先找到father数组下标为0的元素值࿰c;也就是下标为0的节点在树中的直接后继节点也就是父节点的编号࿰c;假设为1࿰c;那么接下来我们就到father数组下标为1位置处查看它所记录的编号为1的直接后继节点的编号是谁࿰c;然后再对应跳转到该father数组的编号位置处࿰c;而我们的根结点的直接后继我们在初始化设置的时候就是它自己࿰c;所以如果我们发现father数组下标为3的记录的直接后继编号就是3࿰c;那么3就是当前的下标为0的元素所处集合的代表元素。
c="https://i-blog.csdnimg.cn/direct/2c4c9a16ce0c4db2ad0b5ac14db8de1e.png#pic_center" alt="在这里插入图片描述" />

那么我们知道了我们查询以及合并的一个原理之后࿰c;那么我们就可以写我们并查集最为关键的两个函数：find函数和union函数࿰c;那么在给处这两个板子之前࿰c;我们还能对并查集的进行两个优化

小挂大：

那么我们除了我们的father数组࿰c;那么我们还可以有我们的size数组࿰c;那么size数组的每个位置和father数组一样对应原数数组当中的每一个位置࿰c;我们size数组的作用则是记录我们每一个集合的元素个数࿰c;那么我们要查找数组下标i位置所处的集合的元素个数࿰c;那么我们就需要调用find函数找到我们下标为i位置的代表元素的下标q࿰c;那么我们查询size[q]࿰c;就可以查到i所处集合中的元素了࿰c;那么所谓的小挂大࿰c;就是我们知道我们合并两个不同的集合࿰c;我们是将其中的一个集合所对应的树给插入到另一个集合对应的树中作为子树࿰c;让该集合的树的根节点的指向修改指向另一个树的根节点来达到

但是我们对于并查集当中的操作࿰c;真正影响时间复杂度的其实是我们的find操作࿰c;因为我们每一次union操作前都要先find来确定完两个集合不相同后࿰c;那么我们只需要将该集合根节点所对应的father数组修改为另一个集合的father数组的值࿰c;而数组由于随机访问࿰c;那么这步修改代价的时间复杂度是o(1),而我们find从当前下标为i的元素在树中往上遍历访问到根节点的时间复杂度则是o(n),所以我们优化时间性能就是尽可能让元素少的集合去插入到元素大的集合中去࿰c;那么这样往上遍历的节点个数就相比于大挂小的节点个数要小࿰c;所以遍历代价就会减小࿰c;这就是我们的小挂大的优化
c="https://i-blog.csdnimg.cn/direct/50bf5eb1a2b845f490dcd088136a3ff8.png#pic_center" alt="在这里插入图片描述" />

路径压缩：

而路径压缩的方式是我们这两个优化中最高效的࿰c;那么我们掌握了路径压缩࿰c;我们甚至都不需要来小挂大来额外建立一个size数组࿰c;但是为了让我们对并查集的理解更全面࿰c;我还是介绍了小挂大的策略

那么我们的路径压缩就是我们当我们执行find操作的时候࿰c;去查询该位置所处集合当中的根节点的时候࿰c;我们会沿途往上遍历直到达到根节点࿰c;那么我们这里在沿途往上遍历的过程中࿰c;我们将我们沿途的每一个节点直接修改连接到根节点࿰c;那么这样我们每一次find的时候࿰c;我们该节点往上遍历就直接是根节点从而直接得到代表元素࿰c;那么每次查询的时间复杂度就可以优化到O(1)!但是我们路径压缩的过程会有一个o(N)的代价࿰c;但是一旦压缩之后࿰c;之后的find都是常数时间复杂度了࿰c;那么这个路径压缩优化下并查集的具体时间复杂度是专门有数学学家花了几十年时间来证明࿰c;那么感兴趣的话࿰c;可以下去自己去了解࿰c;那么这里我就不在赘述了
c="https://i-blog.csdnimg.cn/direct/281a42d52a8248839d99377813e65d90.png#pic_center" alt="在这里插入图片描述" />

而具体我们怎么将我们的沿途的各个节点直接连接根节点࿰c;那么我们就通过栈或者递归来实现࿰c;其中递归的实现原理就是我们的从当前该节点先递归找到根节点࿰c;然后回溯到我们当前节点时࿰c;会依次返回我们根节点的节点编号然后从而修改沿途节点的father数组的值。

find函数递归版本代码板子：

<code class="prism language-cpp">class="token keyword">int class="token function">findclass="token punctuation">(vectorclass="token operator"><class="token keyword">intclass="token operator">>class="token operator">& fatherclass="token punctuation">,class="token keyword">int xclass="token punctuation">)
class="token punctuation">{
	class="token keyword">ifclass="token punctuation">(xclass="token operator">!=fatherclass="token punctuation">[xclass="token punctuation">]class="token punctuation">)
	class="token punctuation">{
		fatherclass="token punctuation">[xclass="token punctuation">]class="token operator">=class="token function">findclass="token punctuation">(fatherclass="token punctuation">[xclass="token punctuation">]class="token punctuation">)class="token punctuation">;
	class="token punctuation">}
	class="token keyword">return fatherclass="token punctuation">[xclass="token punctuation">]class="token punctuation">;
class="token punctuation">}
code>

union函数代码板子：

<code class="prism language-cpp">class="token keyword">void class="token function">_unionclass="token punctuation">(vectorclass="token operator"><class="token keyword">intclass="token operator">>class="token operator">& fatherclass="token punctuation">,class="token keyword">int xclass="token punctuation">,class="token keyword">int yclass="token punctuation">)
class="token punctuation">{
	 class="token keyword">int fxclass="token operator">=class="token function">findclass="token punctuation">(fatherclass="token punctuation">,xclass="token punctuation">)class="token punctuation">;
	 class="token keyword">int fyclass="token operator">=class="token function">findclass="token punctuation">(fatherclass="token punctuation">,yclass="token punctuation">)class="token punctuation">;
	   class="token keyword">ifclass="token punctuation">(fxclass="token operator">!=fyclass="token punctuation">)
	   class="token punctuation">{
	   	fatherclass="token punctuation">[fxclass="token punctuation">]class="token operator">=fyclass="token punctuation">;
	   class="token punctuation">}
	   class="token keyword">returnclass="token punctuation">;
class="token punctuation">}
code>

初始化father数组：

<code class="prism language-cpp">vectorclass="token operator"><class="token keyword">intclass="token operator">> class="token function">fatherclass="token punctuation">(numsclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">)class="token punctuation">; class="token comment">// 创建一个与nums数组大小相同的father数组
class="token keyword">for class="token punctuation">(class="token keyword">int i class="token operator">= class="token number">0class="token punctuation">; i class="token operator">< fatherclass="token punctuation">.class="token function">sizeclass="token punctuation">(class="token punctuation">)class="token punctuation">; iclass="token operator">++class="token punctuation">) class="token punctuation">{
    fatherclass="token punctuation">[iclass="token punctuation">] class="token operator">= iclass="token punctuation">; class="token comment">// 将father数组的每个元素初始化为它自己的索引
class="token punctuation">}
code>

结语

那么这就是本篇并查集的全部内容࿰c;本篇文章就介绍了并查集的原理以及实现࿰c;那么相比于之前我的class="tags" href="/tags/SuanFa.html" title=算法>算法文章࿰c;我还会引入几个与该class="tags" href="/tags/SuanFa.html" title=算法>算法相关的题目来应用࿰c;但是由于博主最近有点忙࿰c;所以就打算将我们的并查集class="tags" href="/tags/SuanFa.html" title=算法>算法篇分为两期࿰c;一期讲原理另一期讲题࿰c;所以这篇文章相比于我们之前的文章来说字数就较少࿰c;那么我下一期我将会讲并查集的相关题目࿰c;我会持续更新࿰c;希望你多多关注࿰c;那么如果本篇文章有帮助到你的话࿰c;还请多多三连关注支持一下博主哦࿰c;你的支持就是我最大的动力！
c="https://i-blog.csdnimg.cn/direct/cb61505ec2184ec18d81a417eb450bcd.png#pic_center" alt="在这里插入图片描述" />