直观理解:并查集(Union-Find Sets)

liuian 2025-07-03 17:02 35 浏览

并查集（Union-Find Sets）是一种简单的树形结构，主要用于解决不相交集合的合并和元素分组查询问题，并查集主要支持两种操作：

合并（Union）：将两个元素合并到同一个集合中。

查询（Find）：查询某个元素所在的集合。

并查集的实现原理非常简单，假设每个元素都是树中的一个节点，每个节点都维护一个指向自己父节点的指针，初始情况下，每个节点的父节点都指向自己，合并两个集合中的元素的时候，只需要不断向上查找，找到两个元素各自的父节点后，将其中一个节点的父节点指向另外一个父节点即可。查找元素所在的集合，只需要不断向上查找，直到找到根节点，根节点元素就是所在集合的标识。下面我们给出简单的find和union的实现过程。

    //用来维护每个顶点对应的集合标识，初始情况下，每个元素的集合都为当前元素
    int[] parent;

    //初始化集合 
    public void init(int size){
        parent = new int[size];
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }
    
    //递归查找父节点，进行路径压缩，并返回根节点
    public int find(int x) {
        if (x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    //合并两个集合
    public void union(int a, int b) {
        parent[find(a)] = find(b);
    }

    //判断两个元素是否在一个集合中
    public boolean isConnected(int a, int b) {
        int A = find(a);
        int B = find(b);
        return A==B;
    }

通过上面的代码我们可以发现，并查集其实是一种非常简单高效的算法，整个算法过程非常容易理解，经常用来处理一些不相交集合的合并及查询问题。

union查询

上一篇：微信生态账号体系-各ID介绍与Unionid的获取
下一篇：点点客刘清剖析微信UnionID和微信登陆

直观理解:并查集(Union-Find Sets)

相关推荐

飞牛OS入门安装遇到问题，如何解决?

如何在 iPhone 和 Android 上恢复已删除的抖音消息

Boost高性能并发无锁队列指南:boost::lockfree::queue

大模型手册: 保姆级用CherryStudio知识库

用什么工具在Win中查看8G大的log文件?

如何在 Windows 10 或 11 上通过命令行安装 Node.js 和 NPM

威联通NAS安装阿里云盘WebDAV服务并添加到Infuse

Trae IDE 如何与 GitHub 无缝对接?

idea插件之maven search(工欲善其事，必先利其器)

如何修改图片拍摄日期?快速修改图片拍摄日期的6种方法