[关闭]
@guoxs 2016-01-22T15:36:41.000000Z 字数 5058 阅读 3587

数据结构之最小生成树

数据结构与算法


5.1 普里姆(Prim)算法

使用邻接矩阵存储网:
普里姆(Prim)算法

邻接矩阵中用65535代表∞

普里姆(Prim)算法代码如下,其中INFINITY为权值极大值,不妨是65535,MAXVEX为顶点个数最大值,此处大于等于9即可。

  1. /* Prim算法生成最小生成树 */
  2. void MiniSpanTree_Prim(MGraph G)
  3. {
  4. int min, i, j, k;
  5. /* 保存相关顶点下标 */
  6. int adjvex[MAXVEX];
  7. /* 保存相关顶点间边的权值 */
  8. int lowcost[MAXVEX];
  9. /* 初始化第一个权值为0,即v0加入生成树 */
  10. /* lowcost的值为0,在这里就是此下标的顶点已经加入生成树 */
  11. lowcost[0] = 0;
  12. /* 初始化第一个顶点下标为0 */
  13. adjvex[0] = 0;
  14. /* 循环除下标为0外的全部顶点 */
  15. for (i = 1; i < G.numVertexes; i++)
  16. {
  17. /* 将v0顶点与之有边的权值存入数组 */
  18. lowcost[i] = G.arc[0][i];
  19. /* 初始化都为v0的下标 */
  20. adjvex[i] = 0;
  21. }
  22. for (i = 1; i < G.numVertexes; i++)
  23. {
  24. /* 初始化最小权值为∞, */
  25. /* 通常设置为不可能的大数字如32767、65535等 */
  26. min = INFINITY;
  27. j = 1; k = 0;
  28. /* 循环全部顶点 */
  29. while (j < G.numVertexes)
  30. {
  31. /* 如果权值不为0且权值小于min */
  32. if (lowcost[j] != 0 && lowcost[j] < min)
  33. {
  34. /* 则让当前权值成为最小值 */
  35. min = lowcost[j];
  36. /* 将当前最小值的下标存入k */
  37. k = j;
  38. }
  39. j++;
  40. }
  41. /* 打印当前顶点边中权值最小边 */
  42. printf("(%d,%d)", adjvex[k], k);
  43. /* 将当前顶点的权值设置为0,表示此顶点已经完成任务 */
  44. lowcost[k] = 0;
  45. /* 循环所有顶点 */
  46. for (j = 1; j < G.numVertexes; j++)
  47. {
  48. /* 若下标为k顶点各边权值小于此前这些顶点未被加入生成树权值 */
  49. if (lowcost[j] != 0 && G.arc[k][j] < lowcost[j])
  50. {
  51. /* 将较小权值存入lowcost */
  52. lowcost[j] = G.arc[k][j];
  53. /* 将下标为k的顶点存入adjvex */
  54. adjvex[j] = k;
  55. }
  56. }
  57. }
  58. }

程序过程详解:

1.程序开始运行,由第4~5行,创建了两个一维数组lowcost和adjvex,    长度都为顶点个数9。它们的作用之后会说明。

2.第6~7行分别给这两个数组的第一个下标位赋值为0,adjvex[0]=0其实意思就是从顶点v0开始(事实上,最小生成树从哪个顶点开始计算都无所谓,这里假定从v0开始),lowcost[0]=0就表示v0已经被纳入到最小生成树中,之后凡是lowcost数组中的值被设置为0就是表示此下标的顶点被纳入最小生成树。

3.第8~12行表示读取上图的右图邻接矩阵的第一行数据。将数值赋值给lowcost数组,所以此时lowcost数组值为{0,10,65535,65535,65535,11,65535,65535,65535},而adjvex则全部为0。此时,已经完成了整个初始化的工作,准备开始生成。

4.第13~36行,整个循环过程就是构造最小生成树的过程。

5.第15~16行,将min设置为了一个极大值65535,它的目的是为了之后找到一定范围内的最小权值。j是用来做顶点下标循环的变量,k是用来存储最小权值的顶点下标。

6.第17~25行,循环中不断修改min为当前lowcost数组中最小值,并用k保留此最小值的顶点下标。经过循环后,min=10,k=1。注意19行if判断的lowcost[j]!=0表示已经是生成树的顶点不参与最小权值的查找。

7.第26行,因k=1,adjvex[1]=0,所以打印结果为(0,1),表示v0至v1边为最小生成树的第一条边。如下图所示。

普里姆(Prim)算法

   8.第27行,此时因k=1,将lowcost[k]=0就是说顶点v1纳入到最小生成树中。此时lowcost数组值为{0,0,65535,65535,65535,11,65535,65535,65535}。

9.第28~35行,j循环由1至8,因k=1,查找邻接矩阵的第v1行的各个权值,与low-cost的对应值比较,若更小则修改low-cost值,并将k值存入adjvex数组中。因第v1行有18、16、12均比65535小,所以最终lowcost数组的值为:{0,0,18,65535,65535,11,16,65535,12}。adjvex数组的值为:{0,0,1,0,0,0,1,0,1}。这里第30行if判断的lowcost[j]!=0也说明v0和v1已经是生成树的顶点不参与最小权值的比对了。

10.再次循环,由第15行到第26行,此时min=11,k=5,adjvex[5]=0。因此打印结构为(0,5)。表示v0至v5边为最小生成树的第二条边,如下图所示。

普里姆(Prim)算法

   11.接下来执行到36行,lowcost数组的值为:{0,0,18,65535,26,0,16,65535,12}。ad-jvex数组的值为:{0,0,1,0,5,0,1,0,1}。

   12.之后,通过不断的转换,构造的过程如下图中图1~图6所示。

普里姆(Prim)算法

假设N=(V,{E})是连通网,TE是N上最小生成树中边的集合。算法从U={u0}(u0∈V),TE={}开始。重复执行下述操作:在所有u∈U,v∈V-U的边(u,v)∈E中找一条代价最小的边(u0,v0)并入集合TE,同时v0并入U,直至U=V为止。此时TE中必有n-1条边,则T=(V,{TE})为N的最小生成树。

由算法代码中的循环嵌套可得知此算法的时间复杂度为

5.2 克鲁斯卡尔(Kruskal)算法

普里姆(Prim)算法是以某顶点为起点,逐步找各顶点上最小权值的边来构建最小生成树的,同样的,也可以以边为目标去构建,因为权值是在边上,直接去找最小权值的边来构建生成树是很自然的想法,只不过构建时要考虑是否会形成环路。此时要用到了图的存储结构中的边集数组结构。以下是edge边集数组结构的定义代码:

  1. /* 对边集数组Edge结构的定义 */
  2. typedef struct
  3. {
  4. int begin;
  5. int end;
  6. int weight;
  7. } Edge;

克鲁斯卡尔(Kruskal)算法
克鲁斯卡尔(Kruskal)算法代码如下:

  1. /* Kruskal算法生成最小生成树 */
  2. /* 生成最小生成树 */
  3. void MiniSpanTree_Kruskal(MGraph G)
  4. {
  5. int i, n, m;
  6. /* 定义边集数组 */
  7. Edge edges[MAXEDGE];
  8. /* 定义一数组用来判断边与边是否形成环路 */
  9. int parent[MAXVEX];
  10. /* 此处省略将邻接矩阵G转化为边集数组edges
  11. 并按权由小到大排序的代码 */
  12. for (i = 0; i < G.numVertexes; i++)
  13. /* 初始化数组值为0 */
  14. parent[i] = 0;
  15. /* 循环每一条边 */
  16. for (i = 0; i < G.numEdges; i++)
  17. {
  18. n = Find(parent, edges[i].begin);
  19. m = Find(parent, edges[i].end);
  20. /* 假如n与m不等,说明此边没有与现有生成树形成环路 */
  21. if (n != m)
  22. {
  23. /* 将此边的结尾顶点放入下标为起点的parent中 */
  24. /* 表示此顶点已经在生成树集合中 */
  25. parent[n] = m;
  26. printf("(%d, %d) %d ", edges[i].begin,
  27. edges[i].end, edges[i].weight);
  28. }
  29. }
  30. }
  31. /* 查找连线顶点的尾部下标 */
  32. int Find(int *parent, int f)
  33. {
  34. while (parent[f] > 0)
  35. f = parent[f];
  36. return f;
  37. }

程序详解:

1.程序开始运行,第5行之后,省略掉颇占篇幅但却很容易实现的将邻接矩阵转换为边集数组,并按权值从小到大排序的代码,也就是说,在第5行开始,已经有了结构为edge,数据内容是上图的右图的一维数组edges。

2.第5~7行,声明一个数组parent,并将它的值都初始化为0。

3.第8~17行,开始对边集数组做循环遍历,开始时,i=0。

4.第10行,调用了第19~25行的函数Find,传入的参数是数组parent和当前权值最小边(v4,v7)的 begin:4。因为parent中全都是0所以传出值使得n=4。

5.第11行,同样作法,传入(v4,v7)的 end:7。传出值使得m=7。

6.第12~16行,很显然n与m不相等,因此parent[4]=7。此时parent数组值为{0,0,0,0,7,0,0,0,0},并且打印得到“(4,7)7”。此时已经将边(v4,v7)纳入到最小生成树中,如下图所示。

克鲁斯卡尔(Kruskal)算法

8.再次执行10~16行,此时i=2,edge[2]得到边(v0,v1),n=0,m=1,parent[0]=1,打印结果为“(0,1)10”,此时parent数组值为{1,0,8,0,7,0,0,0,0},此时边(v4,v7)、(v2,v8)和(v0,v1)已经纳入到最小生成树,如下图:

克鲁斯卡尔(Kruskal)算法

9.当i=3、4、5、6时,分别将边(v0,v5)、(v1,v8)、(v3,v7)、(v1,v6)纳入到最小生成树中,如图下图所示。此时parent数组值为{1,5,8,7,7,8,0,0,6},怎么去解读这个数组现在这些数字的意义呢?

克鲁斯卡尔(Kruskal)算法

从上图的右下方的图i=6的粗线连线可以得到,其实是有两个连通的边集合A与B中纳入到最小生成树中的,如下图所示。当parent[0]=1,表示v0和v1已经在生成树的边集合A中。此时将parent[0]=1的1改为下标,由par-ent[1]=5,表示v1和v5在边集合A中,par-ent[5]=8表示v5与v8在边集合A中,par-ent[8]=6表示v8与v6在边集合A中,par-ent[6]=0表示集合A暂时到头,此时边集合A有v0、v1、v5、v8、v6。我们查看parent中没有查看的值,parent[2]=8表示v2与v8在一个集合中,因此v2也在边集合A中。再由parent[3]=7、par-ent[4]=7和parent[7]=0可知v3、v4、v7在另一个边集合B中。

克鲁斯卡尔(Kruskal)算法

 10.当i=7时,第10行,调用Find函数,会传入参数edges[7].begin=5。此时第21行,parent[5]=8>0,所以f=8,再循环得par-ent[8]=6。因parent[6]=0所以Find返回后第10行得到n=6。而此时第11行,传入参数edges[7].end=6得到m=6。此时n=m,不再打印,继续下一循环。这就是说,因为边(v5,v6)使得边集合A形成了环路。因此不能将它纳入到最小生成树中,如上图所示。

 11.当i=8时,与上面相同,由于边(v1,v2)使得边集合A形成了环路。因此不能将它纳入到最小生成树中,如上图所示。

 12.当i=9时,边(v6,v7),第10行得到n=6,第11行得到m=7,因此parent[6]=7,打印“(6,7)19”。此时parent数组值为{1,5,8,7,7,8,7,0,6},如下图所示。

 13.此后边的循环均造成环路,最终最小生成树即为下图所示。

克鲁斯卡尔(Kruskal)算法

克鲁斯卡尔(Kruskal)算法的实现定义:

假设N=(V,{E})是连通网,则令最小生成树的初始状态为只有n个顶点而无边的非连通图T={V,{}},图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点落在T中不同的连通分量上,则将此边加入到T中,否则舍去此边而选择下一条代价最小的边。依次类推,直至T中所有顶点都在同一连通分量上为止。

此算法的Find函数由边数e决定,时间复杂度为,而外面有一个for循环e次。所以克鲁斯卡尔算法的时间复杂度为

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注