文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++并查集算法简单详解

2024-04-02 19:55

关注

1、并查集的初始化

并查集是用一个数组实现的。首先先定义一个数组:

int father[N];

father[i]表示元素i的父亲结点。

接下来进行初始化。一开始,每个元素都分别是独立的一个集合,父亲结点就是它自己,所以初始化时将所有father[i]等于i:

for(int i = 1; i <= N; i++){
    father[i] = i;
}

 这样,就将father数组初始化完毕。

2、并查集的查找操作

由于规定同一个集合中只存在一个根结点,因此查找操作,就是查找给定结点的根结点的过程。可以通过递推或递归来实现,思路都是一样的,都是反复寻找父亲结点,直到找到根结点为止。

递推代码:

//findFather函数返回元素x所在集合的根结点
int findFather(int x){
    while(x != father[x]){    //如果不是根结点,继续循环
        x = father[x];    //获得自己的父亲结点
    }
    return x;
}

上述代码中, while(x != father[x]),说明当x的父亲结点不等于本身时,也就是x不是根结点时就继续循环,因为父亲结点等于本身这个情况,只有在根结点才会出现。

递归代码:

int findFather(int x){
    if(x == father[x]) return x;    //如找到根结点,就返回根结点编号x
    else return findFather(father[x]); //否则,递归判断x的父亲结点是否是根结点
}

3、并查集的合并操作

合并,就是把两个集合合并成一个集合。实现过程是:先判断两个元素是否属于同一个集合,不属于同一个集合,就开始进行合并操作。判断两个元素是否属于同一个集合的具体思路,就是调用上面的findFather函数,分别查找两个元素所属集合的根结点,根结点不同,则两个元素不属于同一个集合。合并两个集合的具体思路,就是将其中一个集合的根结点的父亲指向另外一个集合的根结点即可。

合并操作的代码实现:(假设有两个集合,一个集合里有元素a,一个集合有元素b)

void Union(int a, int b){
    //让一个集合的根结点的父亲指向另一个集合的根结点
    father(findFather(a)) = findFather(b); 
}

注意,合并操作之前,最好先判断下待合并的两个元素是否位于同一个集合。

4、为什么要路径压缩?

5、实现路径压缩

由于findFather函数目的就是查找根结点,所以,我们在查找结点的路径上直接将所有结点的父亲都指向根结点,查找的时候就不必一直回溯去寻找父亲了,查询的复杂度可以降为O(1)。

比如下面这张图:

观察图不难发现,上图中father[1] = 1,father[2] = 1,father[3] = 2,father[4] = 3。经过路径压缩,就变成下面这幅图:

相当于将所有结点的父亲都直接指向根结点,这就是路径压缩。

如何用代码实现路径压缩呢?以下是具体代码:

int findFather(int x){
    if(father[x] != x) father[x] = findFather(father[x]);
    return father[x];
}

 以上代码,实现了在查询获取根结点的同时,将路径进行压缩优化,代码虽然很短,但是很巧妙,下面解释下上述代码:

 if(father[x] != x),当所查找的元素x的父亲结点不是自己,也就是x不是根结点时,

findFather(father[x]),就继续递归查找父结点,直到找到根结点为止,

father[x] = findFather(father[x]),然后将找到的根结点直接赋给x的父亲结点。

这样就实现了路径压缩,即将结点的父亲直接指向根结点。

return father[x],返回查找到的根结点。

总结

到此这篇关于C++并查集算法简单详解的文章就介绍到这了,更多相关C++并查集算法内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯