好贷网好贷款

并查集算法

发布时间:2016-12-4 22:33:07 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"并查集算法",主要涉及到并查集算法方面的内容,对于并查集算法感兴趣的同学可以参考一下。

所谓并查集,它是一个集合,这个集合的元素也是集合,他支持三种操作: MakeSet(x),建立一个只有一个元素x的集合X0,将这个集合放入并查集中; FindSet(x),在并查集中寻找一个元素S(注意并查集的元素S也是集合) ,满足 x属于S; Union(x,y), 将并查集中的元素S1,S2合并,其中x属于S1,y属于S2。 下面说说并查集的实现,其实很简单,用树来实现。所有属于同一集合的元素属于 同一棵树,这样我们就可以用树根来表示一个集合,要找到某个元素属于哪个集合 ,只要找到这个元素所在的树的树根;要合并两个集合,只要合并两棵树。一般比 较方便的方法是用父亲数组Parent[]来表示树,Parent[i]就是节点i的父结点,树 根的父结点就是它本身。这样很容易根据某个节点找到他的根,也很容易合并两棵 树。但是我们要考虑效率问题。在最坏的情况下,一棵树退化成一个单链表(想象 一下所有的结点只有唯一的儿子节点),这样如果链表长度为L,从一个节点找到 他的根也需要L次运算,对于一共有n个节点元素的并查集,FindSet平均情况和最 坏情况下的复杂度都是O(n),效率并不高。对于一棵树而言,如果树的高度为H, 那麽从叶节点只要经过H次运算就可以找到树根,所以我们应该尽量减少树的高度 ,最好的情况是树的高度只有1层,这样就是一个树根下面有很多儿子,这些儿子 都是树叶。但是如果两棵这样的树合并,数的高度就会增加,比如高度为H1的树 T1和高度为H2的树T2合并,得到的树的高度有两种情况: max { H1, H2+1}或者 max{H1+1, H2},前一种情况是T2的根作为T1的根的儿子,后一种情况则是T1的根 作为T2的根的儿子。这就说明经过多次Union操作以后,树的高度会增加。为了使 得树的高度尽量地小,我们应该将较矮的树合并到较高的树上,因此我们用一个数 rank记录每棵树的高度,rank[i]就是以i为根的子树的高度,在合并的时候就可以 根据rank的值进行合并,Union的代码如下: // 合并x,y所在的集合,并返回交集 int Union(int x, int y) { x = FindSet( x ); // 找到x所在的树的根 y = FindSet( y ); // 找到y所在的树的根 if( x == y ) return x; // -1表示空集 if( x == -1 ) return y; if( y == -1 ) return x; if( Rank[x] > Rank[y] ) { // 将较低的树合并到较高的树上 Parent[y] = x; return x; } else { Parent[x] = y; if( Rank[x] == Rank[y] ) Rank[y]++; // 改变树的高度 return y; } } Union其实是一种启发式算法,rank[i]就是启发函数值。 另外,为了降低树的高度,我们在FindSet的时候也会压缩路径,比如原来a是树根 ,b是a的儿子,c是b的儿子,d是c的儿子,我们调用FindSet(d)找d所在的树的树 根,在找的同时,我们改变该树的结构,使得调用FindSet(d)结束以后树的结构变 为a是树根,b是a的儿子,c也是a的儿子,d也是a的儿子。这就叫做路经压缩。因 此FindSet代码如下: // 返回到元素i所属的集合的代表元素, 同时进行路径压缩 int FindSet(int i) { if( ( i == -1 ) || ( i >= CAPACITY ) ) { // -1表示空集 return -1; } else { if( ( Parent[i] != -1 ) && ( Parent[i] != i ) ) Parent[i] = FindSet( Parent[i] ); // 这句话进行路径压缩 return Parent[i]; } } 并查集的效率很高,可以证明,通过这种树形结构实现的带启发式路径压缩的并查 集,FindSet和Union操作的平均代价是O(lgn),这和二分查找的复杂度一致,可以 证明这已经是理论上最好的算法了,不可能有更好的算法了。如果不进行这种路经 压缩的话,并查集就退化成了链表,在同一链表中的元素属于同一集合,这样的话 FindSet的复杂度是O(n)。 并查集也是很常用的数据结构,有一道题目“亲戚”,也要用并查集: 题目: 亲戚(Relations)   或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女 婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否亲戚应该是可 行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么 检验亲戚关系实非人力所能及。在这种情况下,最好的帮手就是计算机。   为了将问题简化,你将得到一些亲戚关系的信息,如同Marry和Tom是亲戚, Tom和Ben是亲戚,等等。从这些信息中,你可以推出Marry和Ben是亲戚。请写一个 程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。   参考输入输出格式 输入由两部分组成。   第一部分以N,M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的 编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000),每行有两个数ai, bi,表示 已知ai和bi是亲戚。   第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000),每行为ci, di,表示询问ci和di是否为亲戚。   对于每个询问ci, di,若ci和di为亲戚,则输出Yes,否则输出No。   样例输入与输出 输入relation.in 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9 输出relation.out Yes No Yes

上一篇:【Cocos2d-X开发学习笔记】第04期:渲染框架之场景类(CCScene)的使用
下一篇:软件项目流程图绘制工具求教

相关文章

关键词: 并查集算法

相关评论