当前位置: 首页 > article >正文

【图论】并查集的学习和使用

目录

并查集是什么?

举个例子

组成

父亲数组:

find函数:

union函数:

代码实现:

fa[] 初始化code:

find code:

递归实现:

非递归实现:

union code :

画图模拟:

路径压缩:

路径压缩Code:


并查集是什么?

是一种树形的数据结构,一般用来处理集合的合并,查询操作。

举个例子

告诉你1的父节点是2 2的父节点是3 4的父节点是5 6没有父节点 那么可以画出

三个集合,或者说是树 。然后我们一般用并查集判断:①有几棵树 也就是有几个集合 ② 两个点是否同属于一个集合 ③一个点是不是属于这棵树 

组成

主要是通过一个父亲数组和一个find函数、一个union函数实现的。

父亲数组:

记录一个节点的父结点 初始化为自己 也就是一开始自己就是自己的父结点 自己单独属于一个集合

find函数:

根据邻接关系 找到一个结点的根结点 如果两个结点的通过find函数寻找出来的结点相同 则同属一个集合

union函数:

遍历邻接关系时 将两个邻接的结点父亲数组更新的作用 具体来说 判断若两个结点通过find函数寻找出来的根节点不相同 也就是不属于一个集合 则将一个集合并入另一个集合 通过把前一个结点的根节点 的父亲数组 标记为第二个结点的根节点 则两个集合就合并了

代码实现:

fa[] 初始化code:

for(int i=0;i<n;++i)
       fa[i]=i;

find code:

递归实现:

int finds(int a){
    if(a!=fa[a]){
        fa[a]=finds(fa[a]);
    }
    return fa[a];
}

非递归实现:

int finds(int a){
    while(a!=fa[a]){
        a=fa[a];
    }
    return fa[a];
}

详细解释:一个结点 只有父结点是自己 也就是fa[]数组中是自己 才能称为根节点 finds函数就是判断一个结点是否为根结点 如果不是 就继续向上finds他的父节点 看是不是根结点 直到找到根节点 返回 这个根节点可以称之为一个集合的标志

union code :

void unions(int x,int y){
    int fx=finds(x);
    int fy=finds(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}

详细解释:unions函数是用于遍历邻接关系时 更新集合关系。传入两个结点 找到他们的根节点 也就是他们所属集合的标志 判断是否相同 也就是判断是否从属于一个集合 如果不属于一个集合 则把第一个集合的根节点 的父亲结点 更新为 第二个集合的根节点。也就是把第一个集合和第二个集合合并 并且根节点保留为第二个集合的根节点 。

画图模拟:

①我们要判断两个点是否属于一个集合 只要用find函数即可 

②我们要判断共有几个集合 只要看fa数组中有几个 i=fa[i]即可 因为fa[i]等于i 代表是集合里的根结点 一个集合只有一个根结点 所以根结点数即为集合数量

路径压缩:

可以观察到 每次调用find函数都需要经历一串长长的递归 这正是函数时间花费的地方 考虑优化的地方 我们可以直接把fa[i]数组标记为i结点所属集合的根节点 也就是把整条路径上的fa[i]数组都标记为根节点 按上面画图的例题来说 就是把fa[1] fa[3] fa[4] 全部标记为4 这样调用find函数的时候就特别快,一步到位。要想完成这个操作 只要在find函数后加一步 每次find的时候 找到了根节点的值 保存 再用一个while循环向上查找 把整条路径上的结点的fa[]值都更新为找到的根节点 

路径压缩Code:

int new_finds(int a){
    int aa=a;//保存一下查找的点 也就是路径的底部
    if(a!=fa[a]){
        fa[a]=finds(fa[a]);//找到了根节点
    }
    while(aa!=fa[a]){//向上更新整条路径
        int temp=fa[aa];//先存储路径的下一个点
        fa[aa]=fa[a];//路径压缩一个
        aa=temp;//再压缩下一个点
        
    }
    return fa[a];
}


http://www.kler.cn/a/587327.html

相关文章:

  • 背诵--2
  • 如何用Deepseek制作流程图?
  • 2025年1月-3月Java面试题、笔记、简历模版汇总(需要自取)
  • 解锁C++:指针与数组、字符串的深度探秘
  • MySQL复习(检查本地MySQL是否安装、DataGrip数据库可视化工具使用、增删改查基础语法、唯一索引、SQL简单函数)
  • 【科研绘图系列】R语言绘制网络相关图(cor network plot)
  • 11 | 给 Gin 服务器添加中间件
  • Mac下安装Zed以及Zed对MCP(模型上下文协议)的支持
  • PyQt基础——简单闹钟ui实现(图形化界面、定时器事件)
  • C#的简单工厂模式、工厂方法模式、抽象工厂模式
  • Umi-OCR 全家桶
  • C++20 `<bit>` 中的整数 2 的幂运算和 `std::bit_cast`:由浅入深的探索
  • 定制开发开源 AI 智能名片 S2B2C 商城小程序源码在小程序直播营销中的应用与价值
  • matlab 量化交易投资策略研究
  • 基于 Verilog 的 4 位二进制计数器设计与实验:从理论到实践的深度剖析
  • 数据库版本问题导致的查询bug
  • 宇数科技激光雷达L2
  • 3ds Max 鼠标与快捷键组合操作指南
  • 【愚公系列】《高效使用DeepSeek》009-PPT大纲自动生成
  • DeepSeek:为教培小程序赋能,引领行业变革新潮流