找回密码
 立即注册
  • QQ空间
  • 回复
  • 收藏

算法与数据结构---并查集

admin 2019-10-7 22:30 105人围观 C++相关






喜迎国庆





并查集

并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题,可以非常高效的解决连接问题,如网络中节点的连接状态。



并查集支持两个重要的操作是

  • 连接:Union,将两个节点连接起来


  • 查找:Find,找到根节点,用于回答两个节点是否相连


下面介绍一下并查集的实现,借用了bobo老师的一些教学用图,代码的传送门https://github.com/wuatai/dataStructure-Algorithm


1. 基本表示

并查集可以用数组表示,数组的键表示节点,值为一个标记,相同标记的节点表示相连。



上图表示0,1,2,3,4节点相连,5,6,7,8,9节点相连。

实现代码





此实现被称为QuickFind,其中,find函数,直接返回其值,id[i]。

此实现的union操作复杂度为O(n),find操作的复杂度为O(1),当数据量很大的时候效率并不高。

操作20w个数据的连接和查找操作的测试结果如下



2. 并查集的另一种实现

QuickFind的Union操作复杂度为O(n),Find操作复杂度为O(1)。下面介绍一下QuickUnion的实现。

将每个元素看做是一个节点,同样用数组parent表示,parentp[i]表示,i节点的父亲节点是哪个。

初始化时父亲元素都是自己。如图所示。



代码如下





QuickUnion的Union和Find操作的时间复杂度都是O(h),h为树的高度,总体上会比O(n)快不少,与之前的比较1w的数据测试如下



与之前的比较10w的数据测试如下



当数据量大了之后,find操作的量级就会很大,因为一直要找到它的根位置。

极端的情况下是要寻找n次的,而UnionFind只需要一次读取操作,导致了QuickUnion甚至还不如UnionFind。因此需要优化。

问题的关键在于,连接操作parent[pRoot] = qRoot,在进行并操作的时候,不能完全定死,需要根据一些特征来连接,使得并查集形成一个比较平衡的树。

3. 基于size的优化
基于QuickUnion的连接操作完全是固定的,parent[pRoot] = qRoot,没有考虑其他因素,从而可能导致并查集非常不平衡,现在基于size来进行优化。
在Union的时候,每次连接操作都会记录根节点的集合元素个数,通过比较当前根节点下面节点总数的大小,将较小的接入到较大的根节点,这样能让树保持较低的高度。

代码如下







现在来看下测试结果,同样20w的操作。



可以发现效率提高了特别多。

4.基于rank的优化

上面基于size的优化方案,是节点数少的树往节点数多的树合并。

但是节点数多不代表树的高度高,比如按照size的优化方案,执行 Union(2, 5),元素 2 所在的树总节点数有4个,但只有2层;元素 5 所在的树有3个节点,有3层。



这个时候可以使用rank来优化,rank代表数的高度或深度。高度低的树向高度高的树合并。



其他操作与基于size的没有什么变化,主要是union操作。

Union操作代码如下



结果如下,10w的数据2个算法比较几乎没有变化,这是因为,比较难出现层数很高的情况,但是基于rank的并查集应用比size多。



5.基于路径压缩的优化

在执行find的过程中,压缩整棵树的路径,压缩过程如下。



find代码如下



100w的数据,测试结果如下。



可以看到基于路径压缩之后的算法效率比其他两种实现要高许多。



充电快乐,快乐充电



微信:wuatai12138

----------------------------------------------------------------------------------------------------------------------
我们尊重原创,也注重分享,文章来源于微信公众号:阿台的人生加速器,建议关注公众号查看原文。如若侵权请联系qter@qter.org。
----------------------------------------------------------------------------------------------------------------------

鲜花

握手

雷人

路过

鸡蛋

yafeilinux和他的朋友们微信公众号二维码

微信公众号

专注于Qt嵌入式Linux开发等。扫一扫立即关注。

Qt开源社区官方QQ群二维码

QQ交流群

欢迎加入QQ群大家庭,一起讨论学习!

我有话说......