文章作者:Slyar 文章来源:Slyar Home (www.slyar.com) 转载请注明,谢谢合作。
恩,前两周学习了并查集,是时候总结一下了。
等价关系与等价类
从数学上看,等价类是一个对象(或成员)的集合,在此集合中的所有对象应满足等价关系。若用符号"≡"表示集合上的等价关系,那么对于该集合中的任意对象x,y, z,下列性质成立:
1、自反性:x ≡ x
2、对称性:若 x ≡ y 则 y ≡ x
3、传递性:若 x ≡ y 且 y ≡ z 则 x ≡ z
因此,等价关系是集合上的一个自反、对称、传递的关系。
通过金属线连接起来的电器的连通性,就是一种等价关系。这种关系显然具有自反性,因为任何一个器件都是与自身连通的;如果a 电连通b,那么b一定也电连通a,因此这种关系具有对称性; 若a连通到b,并且b连通到c,那么a连通到c 。
并查集
并查集的一般用途就是用来维护某种具有自反、对称、传递性质的关系的等价类。并查集一般以树形结构存储,多棵树构成一个森林,每棵树构成一个集合,树中的每个节点就是该集合的元素,找一个代表元素作为该树(集合)的祖先。
并查集支持以下三种操作:
1、Make_Set(x) 把每一个元素初始化为一个集合
初始化后每一个元素的父亲节点是它本身,每一个元素的祖先节点也是它本身。
2、Find_Set(x) 查找一个元素所在的集合
查找一个元素所在的集合,只要找到这个元素所在集合的祖先即可。判断两个元素是否属于同一集合,只要看他们所在集合的祖先是否相同即可。
3、Union(x,y) 合并x,y所在的两个集合
合并两个不相交集合操作很简单:首先设置一个数组Father[x],表示x的"父亲"的编号。那么,合并两个不相交集合的方法就是,找到其中一个集合的祖先,将另外一个集合的祖先指向它。
并查集的优化
1、Find_Set(x)时 路径压缩
寻找祖先时我们一般采用递归查找,但是当元素很多亦或是整棵树变为一条链时,每次Find_Set(x)都是O(n)的复杂度,有没有办法减小这个复杂度呢?
答案是肯定的,这就是路径压缩,即当我们经过"递推"找到祖先节点后,"回归"的时候顺便将它的子孙节点都直接指向祖先,这样以后再次Find_Set(x)时复杂度就变成O(1)了。
2、Union(x,y)时 按秩合并
即合并的时候将元素少的集合合并到元素多的集合中,这样合并之后树的高度会相对较小。
主要代码实现
1
2
3
4
|
/* father[x]表示x的父节点 */
int father[MAX];
/* rank[x]表示x的秩 */
int rank[MAX];
|
1
2
3
4
5
6
|
/* 初始化集合 */
void Make_Set(int x)
{
father[x] = x;
rank[x] = 0;
}
|
1
2
3
4
5
6
7
8
9
|
/* 查找x元素所在的集合,回溯时压缩路径 */
int Find_Set(int x)
{
if (x != father[x])
{
father[x] = Find_Set(father[x]);
}
return father[x];
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
/* 按秩合并x,y所在的集合 */
void Union(int x, int y)
{
x = Find_Set(x);
y = Find_Set(y);
if (x == y) return;
if (rank[x] > rank[y])
{
father[y] = x;
}
else
{
if (rank[x] == rank[y])
{
rank[y]++;
}
father[x] = y;
}
}
|
分享到:
相关推荐
并查集是一种树型的数据结构,用于处理一些不相交集合的合并问题。 并查集的主要操作有 1-合并两个不相交集合 2-判断两个元素是否属于同一个集合 3-路径压缩
并查集,在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合...并查集是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。常常在使用中以森林来表示。
并查集是一种树型的数据结构,用于处理一些不相交集合的合并问题。 并查集的主要操作有 1-合并两个不相交集合 2-判断两个元素是否属于同一个集合 3-路径压缩
带权并查集(Weighted Union-Find)是一种在数据结构中用于处理不相交集合(Disjoint Set)的算法,它通过合并过程来减少集合的数量,同时考虑合并操作的权重。以下是一个针对带权并查集模板的资源描述: 资源标题...
并查集是一种挺高效的数据结构。实现简单,只是所有元素统一遵从一个规律所以让办事情的效率高效起来。这篇文章主要介绍了数据结构与算法——并查集(不相交集合),需要的朋友可以参考下
按照算法导论的描述的并查集,集合并操作O(1),查找操作O(lgn)的复杂度。
并查集是⼀一种树型的数据结构,⽤用于处理理⼀一些不不相交集合的合并及查询问题。 一个有 n 个结点的连通图的生成树是原图的极小连通子图,且包含原图中的所有 n 个结点,并且有保持图连通的最少的边。最小生成树...
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题(即所谓的并、查)。比如说,我们可以用并查集来判断一个森林中有几棵树、某个节点是否属于某棵树等。 主要构成:并查集主要由一个整型数组...
一种简单的用途广泛的集合. 并查集是若干个不相交集合,能够实现较快的合并和判断元素所在集合的操作,应用很多,如其求无向图的连通分量个数等
并查集是若干个不相交集合,能够 实现较快的合并和判断元素所在集合的操作。一般采取树形结构来存 储并查集,并利用一个rank 数组来存储集合的深度下界,在查找操 作时进行路径压缩使后续的查找操作加速。可以看成是...
并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。 并查集有三种基本操作,获得根节点,判断两节点是否连通,以及将两不连通的节点相连(相当于将两节点各自的集合...
并查集 并查集(Disjoint Set)是一种树型的数据结构,主要用于处理一些不相交集合(disjoint sets)的合并及查询问题。并查集的设计思路是在开始时,每个元素构成一个单元素的集合,然后按照一定顺序将属于同一组的...
董老师的选修课中有一节专题“不相交集合的算法与讨论”,“不相交集合”即为并查集。在刘汝佳的《算法艺术》或其他高级数据结构教材中可找到。我们用森林表示一个并查集,每棵树是一个集合,用树根来标识一个集合。
在一些应用问题中,需要将n个...开始时每个元素自成一个单元素集合,然后按照一定规律将归于同一组元素的集合合并,在此过程中需要反复查询某个元素归属于哪个集合的运算,适合于描述这类问题的抽象数据类型称为并查集
并查集(Union-Find)是一种树型的数据结构,用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。 并查集存在两个操作(1.Union 联合 2.finddeputy 查找代表结点) 和一个需要解答的问题( issameset 是否 ...
董老师的选修课中有一节专题“不相交集合的算法与讨论”,“不相交集合”即为并查集。在刘汝佳的《算法艺术》或其他高级数据结构教材中可找到。我们用森林表示一个并查集,每棵树是一个集合,用树根来标识一个集合。
并查集数据结构:并查集是一种用于处理不相交集合的数据结构,支持合并和查找操作,用于解决集合合并、连通性问题等。 AVL树数据结构:AVL树是一种自平衡的二叉查找树,通过维护节点的平衡因子来保持树的平衡,实现...
并查集 路径压缩思想的应用 STL中的数据结构 vector deque set / map 动态规划 / 记忆化搜索 动态规划和记忆化搜索在思考方式上的区别 最长子序列系列问题 最长不下降子序列 最长公共子序列 一类NP...
并查集用于处理不相交集合,不过这个题目定义很模糊,他也没说是不相交集合,我一开始还以为是有同一个hobby的一群人是一个cluster。 从二部图的角度入手也可以解这个问题。就是看起来比较傻乎乎的。 1114 家族聚类 ...
2012年,作者根据调查的前提向《 Prespacetime Journal》提交了一篇文章,涉及所谓的不相交的开放集消失,导致量子矢量测度不再起作用的问题,即2012年的解决方案是作者指出,量子测度在强制性地,如果使用度量理论...