文章详情

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

请输入下面的图形验证码

提交验证

短信预约提醒成功

C++并查集有哪些常用操作

2023-06-20 14:53

关注

本篇内容介绍了“C++并查集有哪些常用操作”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔细阅读,能够学有所成!

并查集 是一种树型的数据结构,用于处理一些不相加集合的合并和查询问题。在使用中常常以森林来表示。 并查集也是用来维护集合的,和前面学习的set不同之处在于,并查集能很方便地同时维护很多集合。如果用set来维护会非常的麻烦。并查集的核心思想是记录每个结点的父亲结点是哪个结点。

前言

并查集是一种多叉树,用于处理不相交的集合的合并与查询问题(判断)。

通俗理解:在日常生活中,我们会因为某个人是自己的朋友,哪怕是朋友的朋友也是有朋友,会给予通融、 偏袒。而并查集的基本概念,就是判断某两个集合是否是“朋友”关系,并让两个集合成为“朋友”

常用操作

初始化:每个结点单独作为一个集合

查询:求元素所在的集合的代表元素,即根结点

合并:将两个元素所在的集合,合并为一个集合

合并之前,应先判断两个元素是否属于同一集合,用上面的“查询”来实现

算法实现

初始化:初始的时候每个结点各自为一个集合,father[i]表示结点 i 的父亲结点,如果 father[i]=i,我们认为这个结点是当前集合根结点(开始时每个节点根节点是他自己)。

void init() {    for (int i = 1; i <= n; ++i) {        father[i] = i;    }}

查找:查找结点所在集合的根结点,结点 x 的根结点必然也是其父亲结点的根结点(像是有递归的样子)。

int get(int x) {    if (father[x] == x) { // x 结点就是根结点        return x;     }    return get(father[x]); // 如果该节点不是根节点,继续寻找父结点的根结点}

合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。

void hebing(int x, int y) {    x = find(x);    y = find(y);    if (x != y) { // 不在同一个集合        father[y] = x;//将根节点合并    }}

上面三个操作是并查集常用的操作

前面的并查集的复杂度实际上在有些极端情况会很慢。比如树的结构正好是一条链,那么最坏情况下,每次查询的复杂度达到了O(n) 。这并不是我们期望的结果。路径压缩的思想是,我们只关心每个结点的父结点,而并不太关心树的真正的结构(递归查找相当浪费时间)如下:

C++并查集有哪些常用操作

当想去访问6的根节点时,要访问5的根节点,想去访问5的根节点,又要去访问4的根节点..........以此类推,此时并查集退化为线性。

这样我们在一次查询的时候,可以把查询路径上的所有结点的father[i]都赋值成为根结点。只需要在我们之前的查询函数上面进行很小的改动

int findf(int k){     if(f[k] == k)         return k;             return f[k] = findf(f[k]); //后来更新的点的根节点直接为最开始的点,一步找到总根节点。}

“C++并查集有哪些常用操作”的内容就介绍到这里了,感谢大家的阅读。如果想了解更多行业相关的知识可以关注编程网网站,小编将为大家输出更多高质量的实用文章!

阅读原文内容投诉

免责声明:

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

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

软考中级精品资料免费领

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

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

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

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

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

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

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