并查集 算法分析

硅谷探秘者 Md 数据结构,算法基础 571 0 0

[数据结构与算法]

一、简介

wiki上关于并查集的简介

在计算机科学中,并查集是一种树型的数据结构,用于处理一些不交集(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个用于此数据结构的操作:

  • Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
  • Union:将两个子集合并成同一个集合。

并查集主要用于解决动态连通性问题

我们用一个代表来标识一个不交集. 通常我们不关心哪个成员作为代表, 但是对于属于同一个集合的两个变量, 查询应该得到相同的代表。

举个栗子,假如有一个大型的计算机网络, 其中有很多台计算机, 如果计算机a与计算机b连通, b与c连通, 那么a与c连通. 对于网络中的两台计算机p, q我们可能有这些操作: 判断p, q是否连通find(p) == find(q);在p, q之间建立一条路线使两者连通union(p, q)

通过上面的例子不难看出连通是一种等价关系, 它有以下性质:

  • 自反性: p与p是连通的
  • 对称性: p与q连通, 则q与p连通
  • 传递性: p与q连通且q与r连通, 则p与r连通

二、算法实现

首先我们用一个数组记录所有元素, 对于set[i] == k , i表示i个元素, k表示元素所属的集合, 通常可以指向或者间接指向集合的代表来表示属于这个集合. 当set[i] == i是表明i是一个根节点。
set[i] ==k可以理解为i, k之间有一条连通的路线, 被称为链接。

初始化

让所有元素指向自己, 表示属于不同的集合, 此时集合中每个元素都是一个根节点

    private int[] parent;

    public void init(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

Find

从x向上查找, 直到找到元素的根节点set[i] == i, 此根节点就表示这个集合。

    public int find(int x) {
        if (parent[x] != x) {
            find(parent[x]);
        }
        return parent[x];
    }

Union

把两个不同的点连起来, 对于x ,y两个点来说, 相当与把x, y所在集合合并(传递性), 即x, y所在集合所以元素都连通. 所以我们可以找到两个集合的代表(根节点), 然后把代表合并即可。

    public void union(int x, int y) {
        // 分别查询x、y所在集合的代表
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            // 如果存在同一个集合中,则返回
            return;
        }
        // 选取rootY作为新集合的代表,把x所在集合合并到y集合
        parent[rootX] = rootY;
    }

我们在选取谁合并到谁时是随便选取的, 实际上合理的选取能够很好地优化算法。

三、图示

1 2 3 4 5 6 7 8 9 10
1 1 1 9 2 5 9 1 9 7

find(6)即为parent[parent[parent[parent[6]]]] == 1

find(7)即为parent[parent[7]] == 9

union(6, 7)

1 2 3 4 5 6 7 8 9 10
9 1 1 9 2 5 9 1 9 7

rootX = 1, rootY = 9, 即parent[1] = 9

1 2 3 4 5 6 7 8 9 10
9 1 1 9 2 5 9 1 9 7

合并完如图:

四、算法优化

上面提到合并是随意选取的, 那么怎么选取可以优化算法呢. 考虑find算法的过程, 从低向上查找代表, 那么树的高度就决定了find的快慢. 所以我们合并时可以考虑把比较矮的树合并到比较高的树上, 这样可以有效降低树的高度, 从而达到优化算法的目的

启发式合并

定义一个数组rank,记录每个节点的树高度,合并时,让较低的树合并到较高的树上,以达到有效降低树高的目的。

    private int[] rank;//记录树的高度
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return;
        }
        // 比较树高,让较低的树合并到较高的树上
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

图示:

union(6, 7), 因为6所在树比7所在树高且大, 所以此时parent[9] = 1

可以看到相比没有优化的算法, 这种合并方式有效地降低了树高

1 2 3 4 5 6 7 8 9 10
1 1 1 9 2 5 9 1 1 7

路径压缩

既然把树高降低能优化算法, 那么我们能在find中降低树高吗?

我们可以在find中把查找路径上遇到的所有节点都直接链接到根节点, 从而实现路径压缩, 把树高降低。

代码十分简单, 甚至不比上面的复杂. 时间复杂度非常接近但是没有达到1

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

路径压缩图示

合并6、7两棵树union(6, 7)

先会调用find(6), find(7), 查找路径上的所以元素都会直接和根节点链接。

1 2 3 4 5 6 7 8 9 10
1 1 1 9 1 1 9 1 9 7

之后 parent[1] = 9

1 2 3 4 5 6 7 8 9 10
9 1 1 9 1 1 9 1 9 7

五、小结

  • 路径压缩加上启发式合并就是并查集算法的最优解.
  • 一般来说用路径压缩算法就足够了, 可以不再用启发式合并或者加权

评论区
请写下您的评论...
暂无评论...
猜你喜欢
java虚拟机(jvm) 1296 1.标记-清除最基础的收是“标记-清除”(Mark-Sweep),如同它的名字一样,为“标记”和“清除”两个阶段:首先标记出所有需要回收的对象,在标记完成后统一回收所有被标记的对
数据结构与算法 7101 科普:第一篇二搜索论文是1946年发表,然而第一个没有bug的二却是在1962年才出现,中间用了16年的时间。定义在计机科学中,二找(英语:binarysearch),也称折半搜索
spring/springmvc 4085 1.springmvc执行流程图:2.执行流程1.一个url请求该站点的前端控制器DispatcherServlet。2.随后DispatcherServlet调用HandlerMapping
java虚拟机(jvm) 1459 jvm内存模型-垃圾收器和内存配策略(1)说起垃圾收(GarbagcCollcction,GC),大部人都把这项技术当做java语言的伴生产物。事实上,GC的历史比Java久远,1960
数据库 1336 错误日志一般询日志慢询日志官方手册:https://dev.mysql.com/doc/refman/5.7/en/server-logs.html不管是哪个数据库产品,一定会有日志文件。在
java基础 1577 java发编程-理解CAS1.什么是cas?CAS:CompareandSwap,即比较再交换。jdk5增加了发包java.util.concurrent.*,其下面的类使用CAS
java基础 1260 1.HashMap的构造函数1.publicHashMap()publicHashMap(){this.loadFactor=DEFAULT_LOAD_FACTOR;//allotherfieldsdefaulted}构造一个空的HashMap,初始容量为16,负载因子为0.75,负载因子和它的作用将会在下方解释。2.publicHashMap(intinitialCapacity)publicH
java虚拟机(jvm) 2053 位以及程序中出现的问题。下面将详介绍该命令的使用。命令格式:jmap[option]pid(toconnecttorunningprocess)连接到正在运行的进程jmap[option]execu
归档
2018-11  12 2018-12  33 2019-01  28 2019-02  28 2019-03  32 2019-04  27 2019-05  33 2019-06  6 2019-07  12 2019-08  12 2019-09  21 2019-10  8 2019-11  15 2019-12  25 2020-01  9 2020-02  5 2020-03  16 2020-04  4 2020-06  1 2020-07  7 2020-08  13 2020-09  9 2020-10  5 2020-12  3 2021-01  1 2021-02  5 2021-03  7 2021-04  4 2021-05  4 2021-06  1 2021-07  7 2021-08  2 2021-09  8 2021-10  9 2021-11  16 2021-12  14 2022-01  7 2022-05  1 2022-08  3 2022-09  2 2022-10  2 2022-12  5 2023-01  3 2023-02  1 2023-03  4 2023-04  2 2023-06  3 2023-07  4 2023-08  1 2023-10  1 2024-02  1 2024-03  1 2024-04  1
标签
算法基础 linux 前端 c++ 数据结构 框架 数据库 计算机基础 储备知识 java基础 ASM 其他 深入理解java虚拟机 nginx git 消息中间件 搜索 maven redis docker dubbo vue 导入导出 软件使用 idea插件 协议 无聊的知识 jenkins springboot mqtt协议 keepalived minio mysql ensp 网络基础 xxl-job rabbitmq haproxy srs 音视频 webrtc javascript
目录
没有一个冬天不可逾越,没有一个春天不会来临。最慢的步伐不是跬步,而是徘徊,最快的脚步不是冲刺,而是坚持。