资源描述：
《并查集及例题题解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、树结构的并查集采用树结构支持并查集的计算能够满足我们的要求。并查集与一般的树结构不同，每个顶点纪录的不是它的子结点，而是将它的父结点记录下来。下面是树结构的并查集的两种运算方式⑴直接在树中查询⑵边查询边“路径压缩”对应与前面的链式存储结构，树状结构的优势非常明显：编程复杂度低；时间效率高。直接在树中查询集合的合并算法很简单，只要将两棵树的根结点相连即可，这步操作只要O（1）时间复杂度。算法的时间效率取决于集合查找的快慢。而集合的查找效率与树的深度呈线性关系。因此直接查询所需要的时间复杂度平均为O（logN）。但
2、在最坏情况下，树退化成为一条链，使得每一次查询的算法复杂度为O（N）。边查询边“路径压缩其实，我们还能将集合查找的算法复杂度进一步降低：采用“路径压缩”算法。它的想法很简单：在集合的查找过程中顺便将树的深度降低。采用路径压缩后，每一次查询所用的时间复杂度为增长极为缓慢的ackerman函数的反函数——α（x）。对于可以想象到的n，α（n）都是在5之内的。并查集：(union-findsets)是一种简单的用途广泛的集合.并查集是若干个不相交集合，能够实现较快的合并和判断元素所在集合的操作，应用很多。一般采取树形
3、结构来存储并查集，并利用一个rank数组来存储集合的深度下界，在查找操作时进行路径压缩使后续的查找操作加速。这样优化实现的并查集，空间复杂度为O(N)，建立一个集合的时间复杂度为O(1)，N次合并M查找的时间复杂度为O(MAlpha(N))，这里Alpha是Ackerman函数的某个反函数，在很大的范围内（人类目前观测到的宇宙范围估算有10的80次方个原子，这小于前面所说的范围）这个函数的值可以看成是不大于4的，所以并查集的操作可以看作是线性的。它支持以下三中种操作: －Union(Root1,Root2)/
4、/并操作；把子集合Root2并入集合Root1中.要求：Root1和Root2互不相交,否则不执行操作. －Find(x)//搜索操作；搜索单元素x所在的集合,并返回该集合的名字. －UFSets(s)//构造函数。将并查集中s个元素初始化为s个只有一个单元素的子集合. －对于并查集来说，每个集合用一棵树表示。 －集合中每个元素的元素名分别存放在树的结点中，此外，树的每一个结点还有一个指向其双亲结点的指针。 －设S1={0,6,7,8}，S2={1,4,9}，S3={2,3,5}－为简化讨论，忽略实际
5、的集合名，仅用表示集合的树的根来标识集合。 －为此，采用树的双亲表示作为集合存储表示。集合元素的编号从0到n-1。其中n是最大元素个数。在双亲表示中，第i个数组元素代表包含集合元素i的树结点。根结点的双亲为-1，表示集合中的元素个数。为了区别双亲指针信息(≥0)，集合元素个数信息用负数表示。 下标parent集合S1,S2和S3的双亲表示: S1∪S2的可能的表示方法constintDefaultSize=10; classUFSets{//并查集的类定义 private: int*paren
6、t; intsize; public: UFSets(ints=DefaultSize); ~UFSets(){delete[]parent;} UFSets&operator=(UFSetsconst&Value);//集合赋值 voidUnion(intRoot1,intRoot2); intFind(intx); voidUnionByHeight(intRoot1,intRoot2);}; UFSets::UFSets(ints){//构造函数 size=s;
7、parent=newint[size+1]; for(inti=0;i<=size;i++)parent[i]=-1; } unsignedintUFSets::Find(intx){//搜索操作 if(parent[x]<=0)returnx; elsereturnFind(parent[x]); } voidUFSets::Union(intRoot1,intRoot2){//并 parent[Root2]=Root1;//Root2指向Root1 }Find和Union操作性能不
8、好。假设最初n个元素构成n棵树组成的森林，parent[i]=-1。做处理Union(0,1),Union(1,2),…,Union(n-2,n-1)后，将产生如图所示的退化的树。执行一次Union操作所需时间是O(1)，n-1次Union操作所需时间是O(n)。若再执行Find(0),Find(1),…,Find(n-1),若被搜索的元素为i，完成Find(i)操作需要时间为O(i)
