并查集教程文件.ppt

《并查集教程文件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、并查集集合集合是数学中最基本的构造之一，将一组满足某种性质的对象放在一起就形成了集合。集合中包含的对象称为集合中的元素，集合中的元素是无序而且唯一的。人们常用大写英文字母A、B、C等来表示集合,并用x∈A来表示x是集合A中的元素。集合的并、交、差：由A、B集合的全体元素组成的集合为A与B的并集，记作AUB；A与B的公共元素组成的集合称A与B的交集，记作A∩B；属于集合A而不属于集合B的元素组成的集合称为A减B的差，记作A-B。如何实现存储集合中的元素？由于集合中存放的是一组具有相同性质的对象，一般人很容易想到用数组来存储。用数组很容易实现集合类型，但要注

2、意：因为数组一旦定义，其大小就固定不变。所以在定义的时候，要充分考虑最大空间。也可以用链表来存储集合元素。链表可以很容易的动态生成和释放，所以增减节点是很方便的，完全不用考虑象数组那样的长度问题。删除元素也很方便。但是因为涉及到指针，实现起来很容易出错。还可以用vector.它有数组的优点，而且又不必考虑数组那样可能越界的情况。并查集的概念在某些应用中，我们要检查两个元素是否属于同一个集合，或者将两个不同的集合合并为一个集合。这是不相交集合经常处理的两种操作：查找和合并,我们称为并查集。查找find：查找一个指定元素属于哪个集合。对于判断两个元素是否属于

3、同一个集合是非常有用的。合并union：将两个集合合并为1个集合。除了这两个操作之外，还有一个基础的操作——makeset,用于建立只有1个元素的集合。为了更精确的定义上述三个操作，我们需要用一种方法来表示集合。一种通用的做法是选择集合中某个固定的元素作为集合的代表，让他唯一的标识整个集合。一般说来，选取的代表是任意的。也就是说，到底选取集合中的哪个元素作为它的代表是无关紧要的。在并查集中，我们对于集合的表示利用树的思想，一个集合可以看做一棵树，树根即代表该集合的标识。如果两个元素在同一个树中，则它们是同一个集合;合并两个集合，即是对两棵树进行合并。fi

4、nd(x):返回元素x所属集合的代表。为了判断任意两个元素x和y是否属于同一个集合，我们只需要判断find(x)和find(y)是否相等即可，如果相等，说明他们属于同一个集合，否则他们不属于同一个集合。union(x,y):将包含元素x的集合（假设为Sx）和包含元素y的集合（假设为Sy）合并为一个新的集合（即这两个集合的并集），所得到并集可以用它的任何一个元素来做代表，但在实践中，一般都是选择Sx或Sy的代表作为并集的代表。makeset(x):建立一个只包含元素x的集合，显然，此时该集合的代表应该而且只能为x.并查集的实现：（数组）voidmakese

5、t(x){parent[x]=-1;}parent[x]表示x的父亲编号.最开始的，每个元素自成一个集合，即每个元素开始都当做一棵树，其父亲节点初始为-1,表示它没有父亲。intfind(x)//查找x所在的集合。{while(parent[x]!=-1)x=parent[x];returnx;}voidmyunion(intx,inty){intr1=find(x);intr2=find(y);if(height[r1]>height[r2])num[r2]=r1;elseif(height[r1]

6、{num[r1]=r2;height[r2]++;}}思考：如何判断最后所有元素是否属于同一个集合？在以上的实现中，如何更进一步优化？一个集合即是一棵树，在集合中，父子关系实际并不重要，其作用只是通过父亲找到树的根而已，而根也只是集合的标识，树中的任意节点都可以作根。在并查集的实现过程中，树的深度是影响速度的一个重要因素。树的深度越小，则find操作越快，union操作也越快。在union操作中，我们通过height数组已经尽量避免了树的高度增加。但是，我们还可以主动让树的高度减小。改进后的find操作：intfind(intx){if(parent[x

7、]!=-1)parent[x]=find(parent[x]);if(parent[x]==-1)returnx;elsereturnparent[x];}这是路径压缩。它可以在find的过程中，让路径上的元素都成为根的儿子节点。这样，从形式上看，树就从细长型变成了扁平型。并查集的应用实例亲戚若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。第一行：三个整数n,m

8、,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个