kruskal算法的一种改进二分kruskal算法.doc

Kruskal算法的一种改进--二分Kruskal算法 黄荣明 吉林大学软件学院，吉林长春（130012） E-mail：tony513513@ 摘 要：最小生成树是数据结构中图的一个重要部分，它有许多重要的实际应用。如何方便 快捷地找到最小生成树，具有极其重要的现实经济意义。基于此，本文先简单介绍了Prim 算法，Kruskal算法和Sollin算法等经典算法，并提出了对Kruskal算法改进的新算法，命名为 二分Kruskal算法。同时给出了新算法的基本思想，并论证了此算法是正确可行的。接着给 出了新算法的程序实现，然后对新算法和经典Kruskal算法的理论时间代价和实验时间代价 做了详细的比较。最后得出结论：二分Kruskal算法总体上略快于经典Kruskal算法。 关键词：最小生成树；经典Kruskal算法；二分Kruskal算法 1. 引言 赋以权数的图在实际问题中十分有用．根据不同的实际情况，权数的含意可以各不相 同．例如，可用权数代表两地之间道路的长度或行车时间，也可用权数代表某工序所需的加 工时间等． 对于连通的无向图或强连通的有向图，从任一顶点出发周游，或是对于有根的有向图， 从图的根顶点出发周游，可以访问到所有的顶点。周游时经过的边加上所有顶点构成了图的 一个连通子图，称为图的一棵生成树。 对于网络，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并把权 值最小的生成树称为最小生成树(Minimum Spanning Tree，MST)。 构造最小生成树的依据有两条：[1] 1、在网中选择n－1条边连接网的n个顶点； 2、尽可能选取权值为最小的边。 2. 最小生成树的应用 最小生成树问题可以直接用于工程和经济运营的实际中去．如管道的铺设、线路的施工、 运输路线的设计等问题中都涉及最小费用问题．例如： 网络G表示n各城市之间的通信线路网线路（其中顶点表示城市，边表示两 个城市 之间的通信线路，边上的权值表示线路的长度或造价。可通过求该网络的最小生成树达 到求解通信线路或总代价最小的最佳方案。 在生物学研究中，需要对植物和动物分类，对基因进行分类，以获得对种群固有结构 的认识.可以将图论的最小生成树理论引入分子生物学中基因表示数据的聚类分析方 法，设计生成树的表示和基于最小生成树的聚类算法，该方法对研究基因的结构、功 能以及不同种类基因之间的关系都具有重要意义. 3. 经典算法 为了得到最小生成树,人们设计了很多算法,最著名的有Prim算法，Kruskal算法和Sollin算 法。 -1- 3.1 Prim 算法(Prim Algorithm) 设G=(V，E)是具有n个顶点的网络，T=(U，TE)为G的最小生成树，U是T的顶点集合， TE是T的边集合。Prim算法的基本思想是[2] ： （1）从集合V中任取一顶点(例如取顶点v0)放入集合U中，这时U={v0}，TE=NULL。 （2）在所有一个顶点在集合U里，另一个顶点在集合V-U里的边中，找出权最小的 边(u,v)(u∈U，v∈V-U)，将该边放入TE，并将顶点v加入集合U。 （3）重复上述操作直到U=V为止。这时TE中有n-1条边，T=(U，TE)就是G的一棵最小生 成树。显然，Prim算法的时间复杂性为O(n2)，该算法适用于求边稠密网的最小生成树。 3.2 Kruskal 算法(Kruskal Algorithm) Kruskal算法是1956年提出的，俗称“避圈法”。其思想如下[3]： 每次选择n- 1条边，所使用的贪婪准则是：从剩下的边中选择一条不会产生环路的具有 最小耗费的边加入已选择的边的集合中。注意到所选取的边若产生环路则不可能形成一棵生 成树。Kruskal算法分e 步，其中e 是网络中边的数目。按耗费递增的顺序来考虑这e 条边， 每次考虑一条边。当考虑某条边时，若将其加入到已选边的集合中会出现环路，则将其抛弃， 否则，将它选入。 假设G=（V，E）是连通图 （1）令最小生成树的初始状态为只有N个顶点而无边的非连通图T=（V，φ）。 （2）先把图G中的各边按权数从小到大重新排列，并取权数最小的一条边为T中的边。 （3）在剩下的边中，按顺序取下一条边。若该边与T中已有的边构成回路，则舍去该边， 否则选进T 中。 (4) 重复（3），直到有m-1条边被选进T中，这m-1条边就是G的最小生成树。 在图中选择权最小的边，若该边所依附的顶点落在T中不同的连通分量上，则将此边加 入生成树T中；否则，舍去此边，再选择下一条权最小的边。 Kruskal算法的时间复杂性为O(elog2e)，该算法适用于求边稀疏网的最小生成树。 3.3 Sollin 算法(Sollin Algorithm) Sollin算法是众多用于求解MST