基于并查集的克鲁斯卡尔算法在地铁规划中的应用.doc

基于并查集的克鲁斯卡尔算法在地铁规划中的应用 摘要：最小生成树性质优良并应用广泛。针对克鲁斯卡尔算法中的排序、添边、避环等三个重要操作，基于并查集实现了添边与避环操作，通过并查集与排序解决了最小生成树构造过程中所遇到的“回路”问题；基于并查集的克鲁斯卡尔算法提出了一种解决长沙市地铁规划的方案。 关键词：并查集；最小生成树；算法；排序 中图分类号 TP301.6 文献标识码：A 文章编号：1009-3044（2013）18-4236-03 1 概述 最小生成树是当今的热门问题，因其优良的性质和重要的实用价值引起了许多学者的兴趣。有很多学者曾对最小生成树进行过研究，也出现了构造最小生成树的算法。普利姆算法和克鲁斯卡尔算法是两个著名的最小生成树算法。普里姆算法基于顶点，需要用到二叉堆或者类似的数据结构，适合求边稠密的图的最小生成树；而克鲁斯卡尔算法则基于边，用到并查集和排序，适合求边稀疏的图的最小生成树1。克鲁斯卡尔算法容易实现且往往更加高效2。该文利用并查集构造最小生成树，即基于并查集的克鲁斯卡尔算法，并对长沙市的地铁规划问题提出基于并查集的克鲁斯卡尔算法的一种方案。 2 并查集和最小生成树 并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。并查集的精妙之处在于用树来表示集合，并且每棵树的根结点是该树所对应集合的代表元3。并查集主要有3个操作：初始化集合、查找根结点、合并集合。其中初始化操作是将并查集初始化为一片森林，森林中的每棵树仅含有一个根结点；查找根结点的操作是为了找出每个集合的代表元；合并操作则是将两个集合合并为一个集合。 在一个具有几个顶点的连通图G中，如果存在子图G包含G中所有顶点和一部分边，且不形成回路，则称G为图G的生成树，代价最小的生成树则称为最小生成树。 3 基于并查集的克鲁斯卡尔算法 并查集一般用来处理一些不相交集合的合并及查询问题。利用并查集生成最小生成树问题即基于并查集的克鲁斯卡尔算法如下。 初始化并查集； 构造并查集的查找函数； 构造并查集的合并函数； 求出每个顶点与其余各顶点之间的距离； 将这些边按照直线距离从小到大进行排序； 输出最小生成树。 4 基于并查集的克鲁斯卡尔算法的长沙市地铁规划应用 长沙市的地铁规划需要将市区内各个重要的交通站点通过地铁线路连接起来。各个重要站点之间的距离如图1所示。 可以将实际问题抽象为最小生成树的生成问题，然后通过基于并查集的克鲁斯卡尔算法得到最后的最小生成树。先将原图中的各条边按照长度从小到大进行排序，然后利用贪心思维依次选取长度最小但未加入最小生成树的边进行判断，并通过并查集判断是否构成了“回路”。构造最小生成树的过程如表1所示。 按照上述最小生成树的构造过程形成的长沙市地铁规划最小生成树的过程图如图2所示。 上述表明，在长沙市的地铁建设时，首先是将市区的古曲路站与汽车东站两个重要的交通站点连接；第2步是长沙火车站与古曲路站两个重要的交通站点连接；第3步是财经学院站与市政府两个重要的交通站点连接；第4步是芙蓉广场与长沙火车站两个重要的交通站点连接；第5步是汽车西站与财经学院站两个重要的交通站点连接；第6步是财经学院站与芙蓉广场两个重要的交通站点连接；第7步是芙蓉广场与汽车北站两个重要的交通站点连接；第7步是芙蓉广场与省政府两个重要的交通站点连接。这样，按照基于并查集的克鲁斯卡尔算法有效的生成了长沙市地铁规划中的最小生成树。 5 结束语 算法能够实现构造最小生成树。并查集查找和合并的时间复杂度均为常数级，本算法的主要耗时在于排序的操作，而快速排序的时间复杂度为O（nlogn），故本算法的时间复杂度为O（nlogn），适用于求边稀疏图的最小生成树。与传统的克鲁斯卡尔算法相比，算法巧妙地利用并查集来进行“回路”检测，将克鲁斯卡尔算法分解成了并查集和排序两个部分，从而大大简化了最小生成树的实现和在时间上的减少。基于算法解决了长沙市的地铁规划问题，解决了花费最小的代价建设所有的地铁站。 参考文献： 1 严蔚敏，吴伟民.数据结构（C语言版）M.北京：清华大学出版社，2010. 2 Skiena S S，Revilla M A.挑战编程程序设计竞赛训练手册M.刘汝佳，译.北京：清华大学出版社，2009. 3 刘汝佳.算法竞赛入门经典M.北京：清华大学出版社，2009. 4 徐孝凯，贺桂英.数据结构（C语言描述）M.北京：清华大学出版社，2004：10. 5 薛春艳.XUE Chunyan 最小生成树在城市高速公路问题中的应用J.电脑编程技巧与维护2009（6）：30-32. 6 杨勇虎.数据结构（C语言版）M.大连：东软电子出版社，2010：271-284. hdu 1233(贪心算法，克鲁斯卡尔算法，并查集) Time Limit: 4000/2000 MS (Java/Others)Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 25916Accepted Submission(s): 11542Problem Description某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。Input测试输入包含若干测试用例。每个测试用例的第1行给出村庄数目N ( 100 )；随后的N(N-1)/2行对应村庄间的距离，每行给出一对正整数，分别是两个村庄的编号，以及此两村庄间的距离。为简单起见，村庄从1到N编号。当N为0时，输入结束，该用例不被处理。Output对每个测试用例，在1行里输出最小的公路总长度。Sample Input31 2 11 3 22 3 441 2 11 3 41 4 12 3 32 4 23 4 50Sample Output35 Huge input, scanf is recommended.Source思路：考虑的是并查集，还有贪心算法中的克鲁斯卡尔算法，考虑的时候要借助 贪心算法还有并查集，建立树的概念，通过寻找父节点，看是否是满足的父节点，然后进行一些列的判断求解。作者：洛可可代码如下：span style="font-size:14px;"#includestdio.h#includealgorithmusing namespace std;struct disint a,b,c;s10010;int cmp(dis x,dis y)return x.cy.c;int z110;int f(int y)int r=y;while(r!=zr)r=zr;return r;int merge(int a,int b)int fx=f(a);int fy=f(b);if(fx!=fy)if(fxfy)zfy=fx;else zfx=fy;return 1;elsereturn 0;int main()int t,i,n,sum,m;while(scanf("%d",&t),t)n=t*(t-1)/2;for(i=1;i=t;i+)zi=i;for(i=0;in;i+)scanf("%d%d%d",&si.a,&si.b,&si.c);sort(s,s+n,cmp);m=1,sum=0;for(i=0;in&&mt;i+)if(merge(si.a,si.b)m+;sum+=si.c;printf("%d",sum);return 0;/span (function() var s = “_” + Math.random().toString(36).