客户端用不着的数据结构之并查集 | 算法必看系列二十二

简介: 并查集可以看作是一个数据结构,如果你根本没有听说过这个数据结构,那么你第一眼看到 “并查集” 这三个字的时候,脑海里会浮现一个什么样的数据结构呢?拆分来看就是:1、并查集可以进行集合合并的操作(并)2、并查集可以查找元素在哪个集合中(查)3、并查集维护的是一堆集合(集)。

原文链接

并查集

什么是并查集

并查集可以看作是一个数据结构,如果你根本没有听说过这个数据结构,那么你第一眼看到 “并查集” 这三个字的时候,脑海里会浮现一个什么样的数据结构呢?

基于我们之前所学的知识来思考并推导一个问题,这相比直接去理解,你会收获得更多。

我们就来逐字拆解一下,并、查、集 这个三个字,其中前面两个字都是动词,第三个字是个名词。

我们先看名词,因为只有知道了这个东西是什么,才能去理解它能干什么

集就是集合,我们中学时期就学过这个东西,集合用大白话说就是将一堆元素没有顺序地摆放在同一个地方。

现在我们已经知道了其实并查集本质就是集合,那它能做什么呢?这就要看前两个字 – “并” 和 “查”,集合的一些操作想必你肯定记得,例如,交集,并集等等,这里的 “并” 其实就指的是并集操作,两个集合合并后就会变成一个集合,如下所示:

{1,3,5,7} U {2,4,6,8} = {1,2,3,4,5,6,7,8}

那 “查” 又是什么呢?集合本身只是容器,我们最终还是要知道里面存的是什么元素,因此这里的 “查” 是对于集合中存放的元素来说的,我们不仅要查找这个元素在不在集合中,我们还要确定这个元素是在哪个集合中,对于前一个操作,Java 中普通的 set 就可以做到,但是对于后一个操作,仅仅使用一个 set,比较难做到。

好了,现在你应该知道并查集是什么,以及它能干什么了,总结下来就是:

  • 并查集可以进行集合合并的操作(并)
  • 并查集可以查找元素在哪个集合中(查)
  • 并查集维护的是一堆集合(集)

知道了这些后,并查集的概念就清楚了。

并查集的实现

仅仅靠嘴说,还是差点意思,作为程序员,必然是要将我们了解的东西用代码的形式呈现出来。

相信通过上面的表述,你已经知道,并查集维护的是一堆集合而不是一个集合,用什么样的数据结构表示并查集?set 吗?这里有两个东西我们是必须要知道的,元素的值,集合的标号,一个元素仅可能同时存在于一个集合中,元素对集合是多对一的关系,这么看来我们可以用一个健值对的结构来表示并查集,Map 是肯定可以,但是如果对元素本身没有特定要求的话,我们可以使用数组,这样速度更快,使用起来也更加简单,可以看看下面的例子:

{0}, {1}, {2}, {3}, {4}, {5} => [0,1,2,3,4,5]
{0,1,2}, {3,4,5} => [0,0,0,3,3,3] or [1,1,1,4,4,4]
 ...

在解释上面的数组表示方式之前,不知道你有没有发现一个事实就是,“元素本身的值是固定不变的,但是元素所属的集合是可以变化的”,因此我们可以使用数组的 index 来代表元素,数组 index 上存放的值表示元素所属的集合。

另外一个问题就是,集合怎么表示,标号吗?最直接的办法就是就地取材,我们直接从集合中选出一个元素来代表这个集合。相信到这里,你心里还是有存留一堆问题,不急,我们接着看。

说完了集合的表示,我们来看看如何基于这种表示去实现 “并” 和 “查”,也就是集合的合并和元素的查找,这两个操作是相互影响的,因此最好是放在一起讲,合并其实就是改变数组中存放的值,这个值表示的是该元素(index 表示)所在的集合,但是这里有一个问题就是一个集合合并到另一个集合中,我们是不是需要把集合中所有的元素对应的值都更改掉,其实是不需要的,举个例子你就理解了:

{0,1,2}, {3,4}, {5,6} 
=> [1,1,1,3,3,6,6]
{3,4} U {5,6} 
=> {0,1,2}, {3,4,5,6} 
=> [1,1,1,6,3,6,6]{0,1,2} U {3,4,5,6}
=> {0,1,2,3,4,5,6} 
=> [1,6,1,6,3,6,6]

仔细观察,你会发现每次合并操作,我们仅仅更新了代表元素所对应的集合,并没有把整个集合里的元素对应的集合都更改了

“代表元素(根元素)” 也就是代表集合的元素,这个元素所在位置存放的就是其本身,两个集合和并的时候,我们仅仅需要更新代表元素即可,因为查找元素所在集合的过程其实就是查找代表元素的过程,代表元素变了,其余元素对应的集合也就变了

依据上面合并的例子,我们来看看如何查找:

[1,1,1,3,3,6,6] 查找元素 4 所在集合 4 -> 3, 元素 4 在集合 3 里面
[1,1,1,6,3,6,6] 查找元素 4 所在集合 4 -> 3 -> 6,元素 4 在集合 6 里面
[1,6,1,6,3,6,6] 查找元素 0 所在集合 0 -> 1 -> 6, 元素 0 在集合 6 里面

我们在来看看代码的实现,首先是查找:

public int find(int element) {
    if (roots[element] == element) {
        return element;
    }

    int father = element;
    while (roots[father] != father) {
        father = roots[father];
    }

    return father;
}

为了让代码更加简洁,我们也可以写成递归的形式:

public int find(int element) {
    if (roots[element] == element) {
        return element;
    }

    return find(roots[element]);
}

查找就是查找代表元素的过程。

另外就是合并,当两个元素相遇,我们合并是将这两个元素所在的集合进行合并,因此我们依然要借助 find 找到这两个元素所在的集合,如果是相同的集合就不需要合并,不同的集合,就将其中一个代表元素进行更改,使其指向另一个代表元素:

public void union(int element1, int element2) {
    int root1 = find(element1);
    int root2 = find(element2);

    if (root1 != root2) {
        roots[root1] = root2;
    }
}

不知道你有没有思考这个地方为什么数组的名字要命名成 roots,画画图,你会发现并查集其实可以看成是多棵树,也就是森林,只不过这些树的边的方向是从 child 到 parent 的。形象一点解释就是倒着的树。

优化 – 路径压缩

我们可以分析一下上面的代码的时间复杂度,上面的两个函数操作都是基于数组的,其中 union 操作又是依赖于 find 的,因此 find 操作的时间复杂度等同于并查集操作的时间复杂度。首先我们来看一个例子:

{0}, {1}, {2}, {3}, ... {n} => [0,1,2,3,...,n]
{0} U {1} => {1,1,2,3,...,n}
{1} U {2} => {1,2,2,3,...,n}
{2} U {3} => {1,2,3,3,...,n}
...

上面一步步合并,到最后 find(1) 的时间复杂度是 O(n) 的,find 操作的最差时间是 O(n),有没有办法优化呢?有一个路径压缩的思路,还是上面的例子,上面的例子我们最后得到的是一个长长的搜索链:

1 -> 2 -> 3 -> ... -> n

优化的思路就是让这个链变短,如果我们 find(1) 的话,到最后我们可以找到 “代表元素”,但是从 1 到 “代表元素” 中间的所有元素其实都是同一个集合的,从它们开始 find 也都是找的同一个代表元素,那我们是不是可以将 find(1) 找到的代表元素赋值给中间经过的这些元素呢?这样下次,从这些元素直接就可以找到代表元素。也就是将上面的链变成:

1 -> n
2 -> n
3 -> n
...

find 函数优化后就会是:

public int find(int element) {
    if (root[element] == element) {
        return element;
    }

    // 找到代表元素
    int father = element;
    while (root[father] != father) {
        father = root[father];
    }

    // 将路径上所有进过的元素都直接指向代表元素
    int compressPointer = element;
    while (root[compressPointer] != father) {
        int tmp = root[compressPointer];
        root[compressPointer] = father;
        compressPointer = tmp;
    }

    return father;
}

写成递归的形式会比较简洁:

private int find(int element) {
    if (roots[element] == element) {
        return element;
    }

    return roots[element] = find(roots[element]);
}

find 经过路径压缩后时间复杂度会变成 O(1),可能你不太理解为什么这里的时间复杂度是 O(1),代码当中明明就有 while 循环啊。

可以思考一下动态数组的扩容,动态数组就像是 Java 中的 ArrayList 和 C++ 中的 vector,这些动态数组是基于静态数组实现的,一开始的大小不会太大,如果元素装满了,它就会重新开辟一个为原来两倍大小的静态数组,然后把之前的值都拷贝到新的数组中,这一步的 add 操作是 O(n) 的,但是将其均摊到前面 n – 1 步 add 操作,时间复杂度还是 O(1)。同样,思考并查集的时间复杂度的时候也可以往这个方向去想,基于之前的例子 find(1) 一次 O(n) 的操作过后,find(1), find(2), find(3) … 都变成 O(1) 了。

我并不想从数学理论上面去证明,这个非常复杂,有些论文证明说并查集时间复杂度最坏会到 O(logn),也有些论文说时间复杂度是 O(an),这里的 a 是一个极小极小的数,这两种表示方式都没有错,但是并查集退化到 O(logn) 的几率会非常非常的小,只有非常极端的例子才会出现,仅仅记住一个时间复杂度对于我们理解算法本身并没有特别大的帮助。

举个例子,快速排序 作为当今最伟大的 十大算法 之一,我们总说快排的时间复杂度是 O(nlgn),你是否了解过这个算法最差的时间复杂度是 O(n^2) 的,而且不稳定,归并排序稳定且最差时间复杂度是 O(nlgn),但是相比于快排,还是会逊色不少。

可见分析一个算法的性能还是不能仅仅看最差时间复杂度。

如果我们把前面讲到的东西拼接在一起,我们就可以组合成一个真正的并查集结构:

private class UnionFind {
    private int[] roots;

    private UnionFind(int size) {
        this.roots = new int[size];

        for (int i = 0; i < size; ++i) {
            roots[i] = i;
        }
    }

    private int find(int element) {
        if (roots[element] == element) {
            return element;
        }

        return roots[element] = find(roots[element]);
    }

    private void union(int element1, int element2) {
        int root1 = find(element1);
        int root2 = find(element2);

        if (root1 != root2) {
            roots[root1] = root2;
        }
    }
}

并查集还有一个优化叫做启发式合并,就是在 union 操作上优化,之前说过并查集可以看作是一堆倒着的树,这个优化主要是考虑树的深度,合并的时候需要将深度小的树连到深度大的树上面去,因为这个优化对时间的影响并没有路径压缩这么大,因此这里跳过,有兴趣可以了解一下,对于一般的问题,使用路径压缩就完全够了。

并查集可以用来解决什么问题

并查集往往用于解决图上的问题,并查集只有两个操作,“并” 和 “查”,但是通过这两个操作可以派生出一些其他的应用:

  • 图的连通性问题
  • 集合的个数
  • 集合中元素的个数

图的连通性很好理解,一个图是不是连通的是指,“如果是连通图,那么从图上的任意节点出发,我们可以遍历到图上所有的节点”, 这里我们只需要将在图上的节点放到相同的集合中去,然后去看是不是所有的节点均指向同一个集合即可;

集合的个数就是找代表元素的个数,查找某个集合中元素的个数最简单的方式就是直接遍历 roots 数组,然后挨个 find,另外一种方法是在结构中多保存一个数组用来记录每个集合中元素的个数,并根据具体的操作来更改。

反过来我们也要思考一个问题就是,什么问题是并查集所不能解决的?

并查集的合并操作是不可逆的,你可以理解成 只合不分 ,也就是说两个集合合并之后就不会再分开来了,另外并查集只会保存并维护集合和元素的关系,至于元素之间的关系,比如图上节点与节点的边,这种信息并查集是不会维护的,如果遇到题目让你分析诸如此类的问题,那么并查集并不是一个好的出发点,你可能需要往其他的算法上去考虑。

以上是这次的分享,希望对你有所帮助。

作者 | P.yh
来源 | 五分钟学算法

相关文章
|
12天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
23 1
|
16天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
58 4
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
90 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
13天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
13天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
21天前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
82 23
|
21天前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
55 20
|
12天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
37 1
|
21天前
|
机器学习/深度学习 算法 C++
数据结构之鲸鱼算法
鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
42 0
|
21天前
|
算法 vr&ar 计算机视觉
数据结构之洪水填充算法(DFS)
洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
35 0