下载此文档

特殊数据结构——并查集.docx


文档分类:办公文档 | 页数:约6页 举报非法文档有奖
1/6
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/6 下载此文档
文档列表 文档介绍
特殊数据结构——并查集.docx特殊数据结构——并查集在一些有N个元素的集合应用问题中,我们通常是在开始时让每个元素构成一个单元素的集合,然后按一定顺序将屈于同一组的元素所在的集合合并,其间要反复查找一个元素在哪个集合中。这一类问题近几年来反复岀现在信息学的国际国内赛题屮,其特点是看似并不复杂,但数据量极大,若用正常的数据结构来描述的话,往往在空间上过大,计算机无法承受;即使在空间上勉强通过,运行的时间复杂度也极高,根本就不可能在比赛规定的运行时间(1〜3秒)内计算岀试题需要的结果,只能采用一种全新的抽象的特殊数据结构一一并查集来描述。,我们从数学的角度给出等价关系和等价类的定义:定义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|y^SandxRy}给出的集合[x]R 称为由xes生成的一个R的等价类。定义3:若R是集合S上的一个等价关系,则由这个等价关系可产生这个集合的唯一划分。即可以按R将S划分为若干不相交的子集S],S2,S3,Su ,他们的并即为S,则这些子集&变称为S的R等价类。划分等价类的问题的捉法是:要求对S作岀符合某些等价性条件的等价类的划分,已知集合S及一系列的形如“x等价于y”的具体条件,要求给岀S的等价类的划分,符合所列等价性的条件。(我们上而捉到的联系,即可认为是一个等价关系,我们就是要将集合S划分成n个联系的子集,然后再判断x,y是否在一个联系子集中。)二、引题 亲戚(relation)【问题描述】若某个家族人员过于庞大,耍判断两个是否是亲戚,确实还很不容易,现在给出某个亲戚关系图,求任意给出的两个人是否具有亲戚关系。规定:X和y是亲戚,y和Z是亲戚,那么X和Z也是亲戚。如果x,y是亲戚,那么x的亲戚都是y的亲戚,y的亲戚也都是x的亲戚。(人数W5000,亲戚关系W5000,询问亲戚关系次数W5000)。【算法分析】算法1,构造图论模型。结,点即口」①合并1和2用一个n*n的二维数组描述上面的图形,记忆各个点Z间的关系。然后,只要判断给定的两个点是否连通则可知两个元素是否有“亲戚”关系。但要实现上述算法,我们遇到两个困难:空间问题:需要r?的空间,而n高达5000!时间问题:每次判断连通性需要0(n)的处理。该算法显然不理想。并杳集多用于图论问题的处理优化,我们看看并杳集在这里的表现如何。算法2,并杳集的简单处理。我们把一个连通块看作一个集合,问题就转化为判断两个元素是否屈于同一个集合。假设一开始每个元素各口屈于口己的一个集合,每次往图中加一条边a—b,就相当于合并了两个元素所在集合A和B,因为集合A中的元素用过边a-b可[、]t、t/1•A t/9 ■N―1—!b这条边就可以不用加了果合;判断他们所在树的根两个根结点Z间连边②合并1和3判断元素是否属于同一集合:用father[i]表示元素i的父亲结点,如刚才那个图所示:faher[1]:=1;faher[2]:=1;faher[3]:=1;faher[4]:=5;faher[5]:=3至此,我们用上述的算法已经解决了空间的问题,我们不再需要一个I?的空间来记录整张图

特殊数据结构——并查集 来自淘豆网www.taodocs.com转载请标明出处.

相关文档 更多>>
非法内容举报中心
文档信息
  • 页数6
  • 收藏数0 收藏
  • 顶次数0
  • 上传人ttteee8
  • 文件大小57 KB
  • 时间2019-07-21