一 概述
并查集(Disjoint set或者Union-find set)是一种树型的数据结构,常用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。
有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构:
Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union:将两个子集合并成同一个集合。
因为它支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于建立单元素集合。有了这些方法,许多经典的划分问题可以被解决。
为了更加精确的定义这些方法,需要定义如何表示集合。一种常用的策略是为每个集合选定一个固定的元素,称为代表,以表示整个集合。接着。Find(x)返回x所属集合的代表,而Union(x,y)使用两个集合的代表x,y作为参数。
二 主要操作
1.MakeSet(x)
2.Find(x)
3.Union(x,y)
2.1 MakeSet(x) 建立一个新的集合
建立一个新的集合,其唯一成员(因为是其代表)就是x。因为集合是不相交的,故要求x没有在其它集合中出现过。
2.2 Find(x) 包含x集合的代表
返回一个指针,指向包含x的(唯一)集合的代表。
2.3 Union(x,y) 合并两个不相交集合
将包含x和y的动态集合合并成为一个新的集合。所得集合的代表可以是两个集合的任何成员。但在很多情况下,我们一般选择两个集合之前代表中的一个作为新的代表。
三 不相交集合森林(有根树表示集合)
不相交集合可以用链表实现,但是还有一种更快的方法—–有根树表示集合,树中的每个节点都包含集合的一个成员,每棵树都表示一个集合。如下图:
左边的树表示集合{b,c,e,h}其c是代表;右边的树表示集合{d,f,g}其f是代表。
3.1 MakeSet(x)
MakeSet创建一棵仅包含一个节点的树。初始时父节点为自己。
#define N 100
int parent[N];
void MakeSet(int x){
parent[x] = x;
}
3.2 Find(x)
Find(x)指向包含x的(唯一)集合的代表。沿着父节点指针一直找下去,直到找到树根为止。
int Find(int x){
if(x == parent[x]){
return x;
}
Find(parent[x]);
}
3.3 Union(x,y)
Union操作使的一棵树的根指向另一棵树的根。如下图:
void Union(int x,int y){
x = Find(x);
y = Find(y);
parent[y] = x;
}
四 优化
4.1 按秩合并
其思想是使包含较少结点的树指向包含较多结点的树的根。我们并不显示的记录以每个结点为根的子树的大小,而是采用一种能够简化分析的方法。对每个结点,我们用秩表示结点高度(从该结点到某一后代叶节点的最长路径上边的数目)的一个上界。在按秩合并中,具有较小秩的根在Union操作中指向较大秩的根。
rank[x]表示x节点的秩。当由MakeSet创建了一个集合时,对应的树中唯一节点的初始秩为0,每个Find操作都不改变任何秩。
void MakeSet(int x){
parent[x] = x;
rank[x] = 0;
}
当对两棵树应用Union时,有两种情况:
(1) 当两个秩不相等时,我们使具有较高秩的根称为具有较小秩的根的父节点,但秩本身保持不变。
(2)当两个秩相等时,任选一个根作为父节点,并增加其秩的值。
void Union(int x, int y){
x = Find(x);
y = Find(y);
if(x == y) {
return;
}
if(rank[x] > rank[y]){
parent[y] = x;
}
else if(rank[x] < rank[y]){
parent[x] = y;
}
else{
rank[x]++;
}
}
4.2 路径压缩
寻找祖先时,我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find(x)都是O(n)的复杂度。为了避免这种情况,我们需对路径进行压缩,即当我们经过”递推”找到祖先节点后,”回溯”的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find(x)时复杂度就变成O(1)了,如下图所示。可见,路径压缩方便了以后的查找。
其中三角表示子树,其根为所示节点。
int Find(int x){
if(x != parent[x]){
parent[x] = Find(parent[x]);
}
return parent[x];
}
Find是一种两趟方法:一趟是沿查找路径上升,直到找到根;另一趟是沿查找路径下降,一便更新每个节点,使之指向根节点。
五 复杂度分析
空间复杂度为O(N),建立一个集合的时间复杂度为O(1),N次合并M查找的时间复杂度为O(M Alpha(N)),这里Alpha是Ackerman函数的某个反函数,在很大的范围内(人类目前观测到的宇宙范围估算有10的80次方个原子,这小于前面所说的范围)这个函数的值可以看成是不大于4的,所以并查集的操作可以看作是与m成线性关系。
六 应用
并查集常作为另一种复杂的数据结构或者算法的存储结构。常见的应用有:求无向图的连通分量个数,最近公共祖先(LCA),带限制的作业排序,实现Kruskar算法求最小生成树等。
七 引用
并查集
数据结构之并查集
算法导论
<script type="text/javascript">
$(function () {
$('pre.prettyprint code').each(function () {
var lines = $(this).text().split('\n').length;
var $numbering = $('<ul/>').addClass('pre-numbering').hide();
$(this).addClass('has-numbering').parent().append($numbering);
for (i = 1; i <= lines; i++) {
$numbering.append($('<li/>').text(i));
};
$numbering.fadeIn(1700);
});
});
</script>
分享到:
相关推荐
并查集是一种挺高效的数据结构。实现简单,只是所有元素统一遵从一个规律所以让办事情的效率高效起来。这篇文章主要介绍了数据结构与算法——并查集(不相交集合),需要的朋友可以参考下
带权并查集(Weighted Union-Find)是一种在数据结构中用于处理不相交集合(Disjoint Set)的算法,它通过合并过程来减少集合的数量,同时考虑合并操作的权重。以下是一个针对带权并查集模板的资源描述: 资源标题...
按照算法导论的描述的并查集,集合并操作O(1),查找操作O(lgn)的复杂度。
并查集是⼀一种树型的数据结构,⽤用于处理理⼀一些不不相交集合的合并及查询问题。 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树...
并查集 路径压缩思想的应用 STL中的数据结构 vector deque set / map 动态规划 / 记忆化搜索 动态规划和记忆化搜索在思考方式上的区别 最长子序列系列问题 最长不下降子序列 最长公共子序列 一类NP...
并查集 并查集(Disjoint Set)是一种树型的数据结构,主要用于处理一些不相交集合(disjoint sets)的合并及查询问题。并查集的设计思路是在开始时,每个元素构成一个单元素的集合,然后按照一定顺序将属于同一组的...
董老师的选修课中有一节专题“不相交集合的算法与讨论”,“不相交集合”即为并查集。在刘汝佳的《算法艺术》或其他高级数据结构教材中可找到。我们用森林表示一个并查集,每棵树是一个集合,用树根来标识一个集合。
数据结构(广度优先搜索,验证括号匹配,表达式计算,递归的编译,Hash表,分段Hash,并查集,Tarjan算法,二叉堆,左偏树,二斜堆,二项堆,二叉查找树,红黑树,AVL平衡树,Treap,Splay,静态二叉查找树,2-d树,...
| 带权值的并查集 20 | 快速排序 20 | 2 台机器工作调度 20 | 比较高效的大数 20 | 普通的大数运算 21 | 最长公共递增子序列 O(N^2) 22 | 0-1 分数规划 22 | 最长有序子序列(递增/递减/非递增/非递减) 22 ...
董老师的选修课中有一节专题“不相交集合的算法与讨论”,“不相交集合”即为并查集。在刘汝佳的《算法艺术》或其他高级数据结构教材中可找到。我们用森林表示一个并查集,每棵树是一个集合,用树根来标识一个集合。
线段树+树状数组+并查集,转化为排队问题 离散化 离散化矩形切割,矩形覆盖面积统计 覆盖矩形周长统计 离散化矩形切割 灯光投影 搜索 导弹 Bfs+hash状态的抽象,模关系 Bfs变形,钥匙与门 双向广搜 迭代加深 ...
1 5 5 并查集 16 1 6 技术 18 1 6 1 比较 18 1 6 2 排序 18 1 6 3 扫描 19 1 6 4 贪婪算法 20 1 6 5 动态规划算法 20 1 6 6 用整数编码集合 21 1 6 7 二分查找 23 1 7 建议 25 1 8 走得更远 27 第 2 章 字符串 28 2 ...
并查集数据结构:并查集是一种用于处理不相交集合的数据结构,支持合并和查找操作,用于解决集合合并、连通性问题等。 AVL树数据结构:AVL树是一种自平衡的二叉查找树,通过维护节点的平衡因子来保持树的平衡,实现...
并查集用于处理不相交集合,不过这个题目定义很模糊,他也没说是不相交集合,我一开始还以为是有同一个hobby的一群人是一个cluster。 从二部图的角度入手也可以解这个问题。就是看起来比较傻乎乎的。 1114 家族聚类 ...
适⽤场景: 数据量较⼩,需要频繁增加,删除操作的场景 ⼆、⾮线性表 常见的⾮线性表有:树、图、堆 ⾮线性表中数据并不是简单的前后关系。 1.树 树是⼀种数据结构,它是由n(n>=1)个有限节点组成⼀个具有层次关系...
1. 填空 分布式数据库系统按局部数据库管理系统的数据模型分类,可以分为 和 两... 数据分片的方式有以下三种: (1)水平分片:按一定的条件把全局关系的所有元组划分成若干不相交的子集,每个子 集为关系的一个片段。