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

摘 要：最小生成树性质优良并应用广泛.针对克鲁斯卡尔算法中的排序、添边、避环等三个重要操作,基于并查集实现了添边与避环操作,通过并查集与排序解决了最小生成树构造过程中所遇到的“回路”问题；基于并查集的克鲁斯卡尔算法提出了一种解决长沙市地铁规划的方案.

关 键 词：并查集；最小生成树；算法；排序

中图分类号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）,适用于求边稀疏图的最小生成树.与传统的克鲁斯卡尔算法相比,算法巧妙地利用并查集来进行“回路”检测,将克鲁斯卡尔算法分解成了并查集和排序两个部分,从而大大简化了最小生成树的实现和在时间上的减少.基于算法解决了长沙市的地铁规划问题,解决了花费最小的代价建设所有的地铁站.