当前位置：文档之家 › Kruskal算法的一种改进-二分Kruskal算法

Kruskal算法的一种改进-二分Kruskal算法

  • 格式：pdf
  • 大小：453.22 KB
  • 文档页数：13

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算法。

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问题的算法之一，其原理为：算法开始时，图中的n个顶点视为一片森林，每个顶点视为一棵树；算法主循环的流程中，森林里每棵树同时决定其连向其它树的最小邻边，并将这些边加入森林中，实现树的合并；循环到森林中只剩一棵树时终止。

由于森林中树的数目每次至少减少一半，所以只要㏒n次循环就可以找出MST。

[4]因此，Sollin算法的时间复杂性为O(n2log2n)。

4. 二分Kruskal算法基本思想通过对经典Kruskal算法仔细研究和分析，笔者提出了对Kruskal算法改进的一种新算法，根据其思想将其命名为二分Kruskal算法。

假设G=（V,E）是连通图，其中V是G的顶点集合，E是G的边集合。

MST为G的最小生成树。

二分Kruskal算法的基本思想如下：（1） 首先从图G的各边的权值组成序列P中，选择第一个权值K作为轴值，然后将序列分割成两个子序列P1和P2(其中P1包含所有小于或等于轴值K的权值,P2包含所有大于轴值K的权值),根据权值对应于边的原则，分别得到对应于P1的边集E1和对应于P2的边集E2。

（2） 将顶点集分为|V|个等价类，每个等价类包括一个顶点；（3） 对于图G1=(V,E1),以权值的从小到大的顺序处理各条边，如果某条边连接两个不同等价类的顶点，则这条边被添加到MST，两个等价类被合并为一个；反复执行此过程，直到E1种各条边均被考虑过一次；（4） 对于图G而言，此时等价类个数为1+|E2|，以权值的从小到大的顺序处理E2中各条边，如果某条边连接图G中两个不同等价类的顶点，则这条边被添加到MST，两个等价类被合并为一个；反复执行此过程，直到E2中各条边均被考虑过一次。

举例来说，对于下图所示的图图1用二分Kruskal算法，其处理过程如下所示：此图的所有边的权值组成的序列P为{14,10,21,11,19,33,18,7,6,5},选取权值K=14为轴值,将序列P划分为两个子序列P1={10,11,7,6,5}和P2={14,21,19,33,18}，从而得到对应于P1的边集E1={(V1,V2),(V2,V6),(V2,V4),( V3,V4),(V2,V3)}和对应于P2的边集E2={(V4,V6),( V1,V6),( V1,V5),(V5,V6),(V4,V5)}。

根据算法第（3）和（4）步，运用两次经典Kruskal算法的思想，求得最小生成树。

表15. 二分Kruskal算法正确性的证明二分Kruskal算法是对经典Kruskal算法一种改进，其本质是以图G中各边权值组成序列中的第一个记录为轴值，将图G中的边集E划分为E1,E2两个边集（其中E1中各边权值小于等于轴值，E2中各边权值大于轴值），然后用经典Kruskal算法的思想分别对E1,E2所在图G1,G2进行操作。

在二分Kruskal 算法基本思想的每（3）步，即对G 1的操作过程中，由于E 1中各边权值小于等于均值，而经典Kruskal 算法的正确性毋需多言,故用经典Kruskal 算法思想得到的边集E `1，必为MST 的部分边集。

而在基本思想的第（4）步中，由于通盘考虑了第（3）步对图G 的等价类集合的影响，当一条边加入MST 时，它必须满足连接图G （而不是G 2）中两个不同等价类这一条件，故它的加入，不会在MST 中构成回路。

又由于按可按权值从小到大的顺序考虑各边，故第（4）步运用经典Kruskal 算法思想所得的边集E `2，必为MST 除E `1外的另一个部分边集。

所以二分Kruskal 算法是正确的。

6. 二分Kruskal 算法的程序实现//最小生成树的二分Kruskal 算法//参数G 是图，参数MST 是保存最小生成树中所有边的数组 V oid BiKruskal (Graph &G , Edge* &MST) {ParTree A(G .VerticesNum()); //声明等价类变量 MST=new Edge [G .VerticesNum()-1]; //最小生成树int MSTtag=0; //最小生成树边的标号 int n=G .EdgeNum();Gragh G1=G .Vertex[]; //G1,G2初始为图G 的无边顶点集 Graph G2= G .Vertex[];Edge e=G .Edge[0];int Pivot=e.weight; //选择轴值for(i=1;i<n;i++) //分别求 G1,G2，即将边值序列分成两子序列 {int from=G .FromVertex(e); int to=G .FromVertex(e); Edge t=G .Edge[i]; if(Pivot>t.weight)G2.InsertEdge(from,to,t.weight); elseG1.InsertEdge(from,to,t.weight); }Kruskal(G 1,G , MST); Kruskal(G 2,G , MST); }V oid Kruskal (Graph &G1, Graph &G , Edge* &MST)//形参G1用于求最小堆序列，形参G 用于区分不同等价类 {int EdgesNum =G1.EdgesNum(); //声明考虑各边一次的变量 MinHeap<Edge> H(EdgesNum);//最小值堆（minheap ） for(int i=0;i< G1.VerticesNum();i++)//将图的所有边插入最小值堆H 中for(Edge e= G1.FirstEdge(i); G1.IsEdge(e);e= G1.NextEdge(e))if(G1.FromVertex(e)< G1.ToVertex(e)) //因为是无向图，故应防止重复插入 H.Insert(e);While(EdgesNum>0) //合并等价类 {Edge e =H.RemoveMin(); //获得下一条权最小的边 if(e.weight==INFINITY) //边权值为无穷大{Print(“不存在最小支撑树.”); delete []MST;//释放空间 MST=NULL;//MST 是空数组Return; }int from =G .FromVertex(e); //记录该条边的信息 int to =G .ToVertex(e); if(A.Different(from.to)) //如果边e 的两个顶点不在一个等价类{A.Union(from,to); //将边e 的两个顶点所在的等价类合并为一个 AddEdgetoMST(e,MST,MSTtag++); //将边e 加到MST EdgesNum--; } } }//算法结束本算法用到了等价类（父指针表示法的树），最小堆等思想。

合集下载

Kruskal算法的思想、证明及步骤

Kruskal算法的思想、证明及步骤

Kruskal算法的思想、证明及步骤Kruskal算法思想：把n个顶点看成看成n棵分离的树（每棵树只有⼀个顶点），每次选取可连接两个分离树中权值最⼩的边把两个分离的树合成⼀个新的树取代原来的两个分离树，如果重复n-1步后便得到最⼩⽣成树。

Kruskal算法步骤：T0存放⽣成树的边，初值为空C(T0) 最⼩⽣成树的权，初值为0VS 分离树顶点的集合，初值为 { {v1} {v2} … {v n} }A B W分别为边的顶点和权值数组，由⽤户输⼊1) T0←0, C(T0)←0, VS←{ {v1} {v2} … {v n} }, A, B, W按W排序后构成队列Q2) If n(VS)==1 then stop else goto 33) 取Q第⼀组数组(u, v, w) 并从Q中将其删除.4) If u, v 属于同⼀个集合 then goto 3 else 分属两个集合X, Y, goto 5.5) T0←T0∪(u, v), C(T0)←C(T0)+w, VS←VS-X-Y+X∪Y goto 2.Kruskal算法证明：树定义：⽆圈连通图。

引理1：⼀个图是树等价于⼀个图⽆圈且任意不相关联的顶点u, v ，图G+(u, v)则必存在唯⼀⼀个圈。

设由Kruskal算法⽣成的T0序列为e1, e2, e3 … e v-1，假设其不是最⼩⽣成树。

任意最⼩⽣成树T定义函数f(T)：T0中不存在于T中边在T0的下标。

设T1是使f(T)最⼤的变量，设f(T1)=k，即e k不存在于T1中，T1为树且e k不在T1中，所以由引理1得T1+e k必存在圈C，C上必有e,k ≠e k，e,k不在T0中。

现令T2 = T1 - e,k + e k，则T2也为⽣成树但由Kruskal算法可知e k是使e1, e2 … e k-1, e k⽆圈的权值最⼩的边，e1, e2 … e k-1, e ,k是树的⼦图必⽆圈故e,k的权值必定⼩于e k，即T2的总权值不⼤于T1的权值，因T1是最⼩⽣成树，故必T2也是最⼩⽣成树，但f(T2)＞k与k是f函数最⼤取值⽭盾，故T0是最⼩⽣成树。

Kruskal算法

Kruskal算法

最小生成树的Kruskal算法Kruskal算法基本思想：每次选不属于同一连通分量(保证不生成圈)且边权值最小的顶点，将边加入MST，并将所在的2个连通分量合并，直到只剩一个连通分量排序使用Quicksort(O(eloge))检查是否在同一连通分量用Union-Find，每次Find和union运算近似常数Union-Find使用rank启发式合并和路径压缩总复杂度O(eloge)=O(elogv) (因为e<n(n-1)/2)}constmaxn=100;maxe=maxn*maxn;typeedge=recorda,b :integer; //边的2个顶点len :integer; //边的长度end;varedges :array[0..maxe]of edge; //保存所有边的信息p,r :array[0..maxn]of integer; //p保存i的父亲节点，r用来实现Union-Find的rank启发式n,e :integer; //n为顶点数，e为边数procedure swap(a,b:integer); //交换beginedges[0]:=edges[a];edges[a]:=edges[b];edges[b]:=edges[0];end;procedure quicksort(l,r:integer); //快速排序varx,i,j :integer;beginx:=edges[random(r-l+1)+l].len;i:=l;j:=r;repeatwhile edges[i].len<x do inc(i);while edges[j].len>x do dec(j);if i<=j thenbeginswap(i,j);inc(i);dec(j);enduntil i>j;if l<j then quicksort(l,j);if i<r then quicksort(i,r);end;procedure init;vari :integer;beginassign(input,'g.in');reset(input);readln(n,e);for i:=1 to e do readln(edges[i].a,edges[i].b,edges[i].len); //从文件读入图的信息for i:=1 to n do p[i]:=i; //初始化并查集randomize;quicksort(1,e); //使用快速排序将边按权值从小到大排列end;function find(x:integer):integer; //并查集的Find，用来判断2个顶点是否属于一个连通分量beginif x<>p[x] then p[x]:=find(p[x]);find:=p[x]end;procedure union(a,b:integer); //如果不属于且权值最小则将2个顶点合并到一个连通分量vart :integer;begina:=find(a);b:=find(b);if r[a]>r[b] then begin t:=a;a:=b;b:=t end;if r[a]=r[b]then inc(r[a]);p[a]:=b;end;procedure kruskal; //主过程varen :integer; //en为当前边的编号count :integer; //统计进行了几次合并。

Kruskal克鲁斯卡尔最小生成树算法（贪心算法）

Kruskal克鲁斯卡尔最小生成树算法（贪心算法）

Kruskal克鲁斯卡尔最⼩⽣成树算法（贪⼼算法）1. /*2. * Introduction to Algorithms3. * Chapter 23 --- MST.Kruskal4. * Tanky Woo @ 5. * 2012.1.76. */7.8. #include <</span>iostream>9. #include <</span>algorithm>10. using namespace std;11.12. const int maxint = 999999;13.14. typedef struct Road{15. int c1, c2;// a到b16. int value;//权值17. }Road;18.19. int no;20. int line;//记录实际关系数21. Road road[100];//设⼀个⽐较⼤的值，实际看输⼊最⼩⽣成树中：边数e=n-122. int node[101];//最⼩⽣成树：n顶点数23.24. bool myCmp(const Road &a,const Road &b)25. {26. if(a.value <</span> b.value)27. return 1;28. return 0;29. }30.31. //node[2]=1 node[8]=1 ,node[3]=1,共同的祖先,如果(3,8)加进去，则构成回路，不要32. //有点像并查集33. int Find_Set(int n)34. {35. if(node[n]==-1)36. return n;37. return node[n]= Find_Set(node[n]);38. }39.40. bool Merge(int s1,int s2)41. {42. int r1 = Find_Set(s1);43. int r2 = Find_Set(s2);44. if(r1 == r2)//如果相等证明构成回路，则直接返回⼀个0,不要把顶点加进来(下⼀步是加进去的)45. return 0;46. if(r1 <</span> r2)47. node[r2]= r1;48. else49. node[r1]= r2;50. return 1;51. }52.53. int main()54. {55. freopen("input.txt","r", stdin);56. //初始化全为-157. memset(node,-1, sizeof(node));58. scanf("%d",&no);59. scanf("%d",&line);60. int i;61. for(i=0; i<</span>line; ++i)62. {63. cin >> road[i].c1 >> road[i].c2 >> road[i].value;64. }65. sort(road, road+line, myCmp);66. int sum = 0, count = 0;// sum是MST的值，count是记录已使⽤的点数67. for(i=0; i<</span>line; ++i)68. {69. if(Merge(road[i].c1, road[i].c2))//如果返回的为0,则证明构成回路，不要加进70. {71. count ++;72. sum += road[i].value;73. }74. if(count == no-1)//e=n-1已经连通，可以退出75. break;76. }77. cout <</span><</span> sum <</span><</span> endl;78. return 0;79. }80.81.82. /*83. input.txt:84. 985. 1486. 1 2 487. 1 8 888. 2 3 889. 2 8 1190. 3 4 791. 3 6 492. 3 9 293. 4 5 994. 4 6 1495. 5 6 1096. 6 7 297. 7 8 198. 7 9 699. 8 9 7100. */。

第11周图(下)第2讲-求最小生成树的Kruskal算法

第11周图(下)第2讲-求最小生成树的Kruskal算法


Prim （从v4 开始） ：
1：(v1,v4)，2：(v1,v3) 或(v3,v4) ， 不可能是 (v2,v3)
答案为C
━━本讲完━━
（2）将图G中的边按权值从小到大的顺序依次选取： 若选取的边未使生成树T形成回路，则加入TE； 否则舍弃，直到TE中包含(n-1)条边为止。
0 28 1
10
14
16
5
6
2
24
18
25
12
4
3
22
有条件地加入
0
1
(n-1)条边
5
6
2
4
3
TE={}
Kruskal算法示例的演示
0 28 1
10
14
//k表示当前构造生成树的第几条边 //E中边的下标,初值为0 //生成的边数小于n时循环
{
u1=E[j].u;v1=E[j].v;
//取一条边的头尾顶点
sn1=vset[u1];
sn2=vset[v1]; if (sn1!=sn2)
//分别得到两个顶点所属的集合编号 //两顶点属于不同的集合
{ printf(" (%d,%d):%d\n",u1,v1,E[j].w);
0
33
2 20
在实现克鲁斯卡尔算法Kruskal()时，用数组E存放图G中的所有 边，其类型如下：
typedef struct { int u; //边的起始顶点
int v; //边的终止顶点 int w; //边的权值 } Edge;
Edge E[MAXV];
void Kruskal(MGraph g)
图采用哪种存储结构更合适？
邻接矩阵