并查集简介_并查集个人资料_并查集微博_百科网
A-A+

并查集简介_并查集个人资料_并查集微博

2016-12-01 18:20:26 科学百科 阅读 2 次

 

概念/并查集 编辑

如果:给出各个元素之间的联系,要求将这些元素分成几个集合,每个集合中的元素直接或间接有联系。在这类问题中主要涉及的是对集合的合并和查找,因此将这种集合称为并查集。

 

其他/并查集 编辑

链表被普通用来计算并查集.表中的每个元素设两个指针:一个指向同一集合中的下一个元素;另一个指向表首元素。

链结构的并查集

采用链式存储结构,在进行集合查找时的算法复杂度仅为O(1);但合并集合时的算法复杂度却达到了O(n)。如果我们希望两种基本操作的时间效率都比较高的话,链式存储方式就“力不从心”了。

树结构的并查集

采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同,每个顶点纪录的不是它的子结点,而是将它的父结点记录下来。下面是树结构的并查集的两种运算方式

⑴直接在树中查询
⑵边查询边“路径压缩”

对应与前面的链式存储结构,树状结构的优势非常明显:编程复杂度低;时间效率高。

直接在树中查询

集合的合并算法很简单,只要将两棵树的根结点相连即可,这步操作只要O(1)时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O(logN)。但在最坏情况下,树退化成为一条链,使得每一次查询的算法复杂度为O(N)。

边查询边“路径压缩

其实,我们还能将集合查找的算法复杂度进一步降低:采用“路径压缩”算法。它的想法很简单:在集合的查找过程中顺便将树的深度降低。采用路径压缩后,每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数——α(x)。对于可以想象到的n,α(n)都是在5之内的。



并查集(union-find sets)是一种简单的用途广泛的集合.它支持以下三中种操作:  -Union (Root1, Root2) //并操作;把子集合Root2并入集合Root1中.要求:Root1和 Root2互不相交,否则不执行操作.  -Find (x) //搜索操作;搜索单元素x所在的集合,并返回该集合的名字.  -UFSets (s) //构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合.  -对于并查集来说,每个集合用一棵树表示。  -集合中每个元素的元素名分别存放在树的结点中,此外,树的每一个结点还有一个指向其双亲结点的指针。