资源描述：
《特殊数据结构——并查集》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、特殊数据结构——并查集在一些有N个元素的集合应用问题中，我们通常是在开始时让每个元素构成一个单元素的集合，然后按一定顺序将屈于同一组的元素所在的集合合并，其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复岀现在信息学的国际国内赛题屮，其特点是看似并不复杂，但数据量极大，若用正常的数据结构来描述的话，往往在空间上过大，计算机无法承受；即使在空间上勉强通过，运行的时间复杂度也极高，根本就不可能在比赛规定的运行时间（1〜3秒）内计算岀试题需要的结果，只能采用一种全新的抽象的特殊数据结构一一并查集来描述。一.数学准备首先，我们从数学的角度给出
2、等价关系和等价类的定义：定义1：如果集合S屮的关系R是自反的，对称的，传递的，则称他为一个等价关系。自反：x=x；对称：若x=y,贝ijy=x；传递：x=y>y=z,贝ijx=zo要求：x、y、z必须要同一个子集中。定义2：如果R是集合S的等价关系。对于任何xes,由[x]R={y
3、y^SandxRy}给出的集合[x]R称为由xes生成的一个R的等价类。定义3：若R是集合S上的一个等价关系，则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S],S2,S3,Su,他们的并即为S,则这些子集&变称为S的R等价类。划分
4、等价类的问题的捉法是：要求对S作岀符合某些等价性条件的等价类的划分，已知集合S及一系列的形如“x等价于y”的具体条件，要求给岀S的等价类的划分，符合所列等价性的条件。（我们上而捉到的联系，即可认为是一个等价关系，我们就是要将集合S划分成n个联系的子集，然后再判断x,y是否在一个联系子集中。）二、引题亲戚（relation）【问题描述】若某个家族人员过于庞大，耍判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。规定：X和y是亲戚，y和Z是亲戚，那么X和Z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y
5、的亲戚，y的亲戚也都是x的亲戚。（人数W5000,亲戚关系W5000,询问亲戚关系次数W5000）。【算法分析】1.算法1，构造图论模型。结，点即口」①合并1和2用一个n*n的二维数组描述上面的图形，记忆各个点Z间的关系。然后，只要判断给定的两个点是否连通则可知两个元素是否有“亲戚”关系。但要实现上述算法，我们遇到两个困难：(1)空间问题：需要r?的空间，而n高达5000!(2)时间问题：每次判断连通性需要0(n)的处理。该算法显然不理想。并杳集多用于图论问题的处理优化，我们看看并杳集在这里的表现如何。1.算法2,并杳集的简单处理。我们把一个
6、连通块看作一个集合，问题就转化为判断两个元素是否屈于同一个集合。假设一开始每个元素各口屈于口己的一个集合，每次往图中加一条边a—b,就相当于合并了两个元素所在集合A和B,因为集合A中的元素用过边a-b可［、］t、t/1•At/9■N―1—a9.以空!b这条边就可以不用加了果合;判断他们所在树的根两个根结点Z间连边②合并1和3(1)判断元素是否属于同一集合：用father[i]表示元素i的父亲结点，如刚才那个图所示：faher[1]:=1；faher[2]:=1；faher[3]:=1；faher[4]:=5；faher[5]:=3至此，我们用
7、上述的算法已经解决了空间的问题，我们不再需要一个I?的空间来记录整张图的构造，只需要用一个记录数组记录毎个结点属于的集合就可以To但是仔细思考不难发现，毎次询问两个元素是否属于同一个集合我们最多还是需要0(n)的判断！1.算法3,并查集的路径压缩。算法2的做法是指就是将元素的父亲结点指来指去的在指，当这课树是链的时候，可见判断两个元素是否属于同一集合需要0(n)的时间，于是路径压缩产生了作用。路径压缩实际上是在找完根结点之后，在递归冋来的时候顺便把路径上元素的父亲指针都指向根结点。这就是说，我们在“合并5和3”的时候，不是简单地将5的父亲指向
8、3,而是直接指向根节点1，如图：由此我们得到了一个复杂度只是0(1)的算法。K程序清单』(1)初始化：fori:=1tondofather[i]:=i;因为每个元素屈于单独的一个集合，所以每个元素以口己作为根结点。(2)寻找根结点编号并压缩路径：functiongctfathcr(v:intcgcr):integer;beginiffather[v]=vthencxit(v);father[v]:=gctfather(father[v]);gctfathcr:^father[v];end;(3)合并两个集合：proccudrcmerge(x,
9、y:intcgcr);beginx:=gctfathcr(x);y:=gctfathcr(y);fathcr[x]:二y;end;(4)判断元素是否属于同一结合：f
