并查集

简介:

 并查集

     并查集是一种简单的用途广泛的集合。并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作。应用很多,如其求无向图的连通分量个数等。最完美的应用当属:实现Kruskar算法求最小生成树。并查集的精髓在于三个操作:初始化,查找,合并。

1.三个操作

  (1)初始化Make_Set()

   初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身(也可以根据情况而变)。

  (2)查找Find_Set(x)

   查找一个元素所在的集合,其精髓是找到这个元素所在集合的祖先!这个才是并查集判断和合并的最终依据。判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。合并两个集合,也是使一个集合的祖先成为另一个集合的祖先。

  (3)Union(x,y)

  合并两个不相交集合操作很简单,利用Find_Set找到其中两个集合的祖先,将一个集合的祖先指向另一个集合的祖先。

2.并查集的优化

  (1)Find_Set(x)时 路径压缩
   寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回溯"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了,如下图所示;可见,路径压缩方便了以后的查找。

 (2)Union(x,y)时按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。

 

简易版本

复制代码
int bin[50001];

void set()       //初始化,使每个节点的祖先节点都是它本身
{
    int i;
    for(i=0;i<50001;i++)        
    {    
        bin[i]=i;        
    }    
}

int find(int x)    //查找x的祖先节点
{
    int r=x;
    while(r!=bin[r])
        r=bin[r];
    return r;    
}

void merge(int x,int y)   //合并x和y
{
    int fx,fy;
    fx=find(x);
    fy=find(y);
    if(fx!=fy)
        bin[fx]=fy;    
}
复制代码

优化版本

复制代码
int father[MAX];   //father[x]表示x的父节点
int rank[MAX];    //rank[x]表示x的秩


void Make_Set(int x)  //初始化集合
{
    int i;
    for(i=0;i<MAX;i++)
    { 
        father[x] = x; 
        rank[x] = 0;   
    }  
}

int Find_Set(int x)        //查找x元素所在的集合,回溯时压缩路径
{
    if (x != father[x])
    {
        father[x] = Find_Set(father[x]); //回溯时压缩路径
    }
    return father[x];
}


void Union(int x, int y)   //合并
{
    x = Find_Set(x);
    y = Find_Set(y);
    if (x == y) return;
    if (rank[x] > rank[y])   //如果x的秩大于y的秩
    {
        father[y] = x;      //y指向x
    }
    else
    {
        if (rank[x] == rank[y])
        {
            rank[y]++;
        }
        father[x] = y;
    }
}
复制代码
相关文章
|
存储 Linux 开发工具
Rockchip系列之浅度分析UART接口系列(1)
Rockchip系列之浅度分析UART接口系列(1)
1033 1
|
6月前
|
存储 人工智能 Kubernetes
ACK Gateway with AI Extension:面向Kubernetes大模型推理的智能路由实践
本文介绍了如何利用阿里云容器服务ACK推出的ACK Gateway with AI Extension组件,在Kubernetes环境中为大语言模型(LLM)推理服务提供智能路由和负载均衡能力。文章以部署和优化QwQ-32B模型为例,详细展示了从环境准备到性能测试的完整实践过程。
|
12月前
|
缓存 JavaScript 前端开发
三个小时vue3.x从零到实战(vue3.x面试总结)
该文章总结了Vue 3.x面试中常见的知识点和问题,包括Vue的生命周期、核心概念、组件通信方式等方面的内容,有助于准备Vue相关技术面试。
146 0
|
消息中间件 存储 安全
RabbitMQ 常用 API(一)
RabbitMQ 常用 API(一)
327 0
|
11月前
|
SQL 数据库
DBeaver执行sql文件
本文介绍了DBeaver这款支持多种数据库的通用数据库管理工具和SQL客户端,它具备查看数据库结构、执行SQL查询和脚本、浏览和导出数据等功能。
1390 1
DBeaver执行sql文件
|
机器学习/深度学习 JSON API
【Python奇迹】FastAPI框架大显神通:一键部署机器学习模型,让数据预测飞跃至Web舞台,震撼开启智能服务新纪元!
【8月更文挑战第16天】在数据驱动的时代,高效部署机器学习模型至关重要。FastAPI凭借其高性能与灵活性,成为搭建模型API的理想选择。本文详述了从环境准备、模型训练到使用FastAPI部署的全过程。首先,确保安装了Python及相关库(fastapi、uvicorn、scikit-learn)。接着,以线性回归为例,构建了一个预测房价的模型。通过定义FastAPI端点,实现了基于房屋大小预测价格的功能,并介绍了如何运行服务器及测试API。最终,用户可通过HTTP请求获取预测结果,极大地提升了模型的实用性和集成性。
754 1
|
数据可视化 搜索推荐 JavaScript
SonarQube:解析代码质量,提升开发效率
在软件开发领域,代码质量管理是至关重要的。本文将介绍静态代码分析工具 SonarQube 的概念与实践,探讨其在代码质量管理中的作用和优势。我们将深入理解 SonarQube 的工作原理,了解如何通过该工具检测、评估和改善代码质量,以提高软件开发效率和可维护性。
|
索引 Python
技巧 | 5000字超全解析Python三种格式化输出方式【% / format / f-string】
技巧 | 5000字超全解析Python三种格式化输出方式【% / format / f-string】
|
JavaScript 前端开发
Form表单利用Jquery Validate验证以及ajax提交
Form表单利用Jquery Validate验证以及ajax提交
212 0
|
NoSQL Java API
新来个技术总监:谁再用Redis实现订单超时自动关闭,以后就不用来了! 下
新来个技术总监:谁再用Redis实现订单超时自动关闭,以后就不用来了! 下