图结构中寻找最小生成树的一种算法--Prim算法

gong

发布日期: 2020-08-24 15:51:30 浏览量: 176
评分:
star star star star star star star star star star_border
*转载请注明来自write-bug.com

普里姆算法是图结构中寻找最小生成树的一种算法。所谓生成树,即为连通图的极小连通子图,其包含了图中的n个顶点,和n-1条边,这n个顶点和n-1条边所构成的树即为生成树。当边上带有权值时,使生成树中的总权值最小的生成树称为最小代价生成树,简称最小生成树。最小生成树不唯一,且需要满足一下准则:

  • 只能使用图中的边构造最小生成树

  • 具有n个顶点和n-1条边

  • 每个顶点仅能连接一次,即不能构成回路

  • 获得图的最小生成树,即在保证图中所有顶点不重复连通的情况下,使得总权值最小

如何使总权值最小?

通过构造邻接矩阵找最小总权值,如图1右边所示。邻接矩阵中保存了顶点之间的连通关系和权值大小,我们可以构造最小代价数组lowcost[n]来记录图中与各顶点相连的最小权值(其中n为顶点数)。再构造顶点编号数组adjvex[],用于记录lowcost中权值所对应的顶点编号。初始化lowcost数组为邻接矩阵中第一行,即lowcost[] = {0,10,#,#,#,11,#,#,#} (这里用“#”表示图中无穷)。除去起始顶点v0外,其余为n-1条边的权值。我们将v1行的权值与lowcost数组中保存的权值对比,如果对应的权值比lowcost中的小,则替换之,这里比较后得到的lowcost[] = {0,10,18,#,#,11,16,#,12}。依次遍历邻接矩阵中剩余的v2到v8,即可得到总权值最小的lowcost数组。

但是,这样虽然保证了总权值最小,但是不能保证所有节点是连通的。

由lowcost数组可以知道,权值为“#”是无效权值,即与当前顶点不相连的顶点,权值为0表示顶点本身或者说是已经匹配到的相连的最小权值点。在每次重建lowcost数组之后,遍历数组中的权值,将权值最小的项置为0,表示对应顶点已经匹配到了权值最小的边。并记录该顶点的编号为minId,下次更新lowcost数组从minId开始搜寻,以此类推。比如,初始化lowcost后将权值最小的顶点,即v1置为0,得到lowcost[] = {0,0,#,#,#,11,#,#,#},minId = 1。之后,从v1开始替换lowcost中的权值。当lowcost中所有的权值都置为0时,即所有顶点都连通且保证总权值最小。

  1. public class Prim {
  2. public static void main(String[] args) {
  3. int min = Integer.MAX_VALUE; //定义min变量保存每一个lowcost数组中的最小值,默认为无效权值
  4. int minId = 0;//定义minId变量保存最小权值的顶点编号
  5. int sum = 0;//定义sum变量记录总权值
  6. String[] Vertex = new String[] { "A", "B", "C", "D", "E", "F" }; //顶点集
  7. int[][] Matrix = new int[6][]; //邻接矩阵
  8. //邻接矩阵初始化
  9. Matrix[0] = new int[] { 0, 7, 5, 1, min, min };
  10. Matrix[1] = new int[] { 7, 0, min, 6, 3, min };
  11. Matrix[2] = new int[] { 5, min, 0, 7, min, 2 };
  12. Matrix[3] = new int[] { 1, 6, 7, 0, 6, 4 };
  13. Matrix[4] = new int[] { min, 3, min, 6, 0, 7 };
  14. Matrix[5] = new int[] { min, min, 2, 4, 7, 0 };
  15. int vertexSize = Vertex.length;//顶点个数
  16. int lowcost[] = new int[vertexSize];//定义最小代价矩阵
  17. int adjvex[] = new int[vertexSize];//定义数组保存最小权值的顶点编号
  18. //lowcost矩阵初始化
  19. for(int i=0;i<vertexSize;i++) {
  20. lowcost[i] = Matrix[0][i];
  21. }
  22. for(int i=1;i<vertexSize;i++) {
  23. min = Integer.MAX_VALUE;
  24. minId = 0;
  25. for(int j=1;j<vertexSize;j++) {
  26. if(lowcost[j]!=0&&lowcost[j]<min) {//找到lowcost中的最小有效权值
  27. min = lowcost[j];//记录最小值
  28. minId = j;//记录最小权值的顶点编号
  29. }
  30. }
  31. lowcost[minId] = 0;
  32. sum += min;
  33. System.out.println("连接顶点:" +Vertex[adjvex[minId]]+" 权值:" +min);
  34. for(int j=1;j<vertexSize;j++) {
  35. if(lowcost[j]!=0&&Matrix[minId][j]<lowcost[j]) {//在邻接矩阵中以编号为minId的顶点作为下一个顶点对lowcost中进行最小值替换
  36. lowcost[j] = Matrix[minId][j];
  37. adjvex[j] = minId;
  38. }
  39. }
  40. }
  41. System.out.println("总权值为:" + sum);
  42. }
  43. }
上传的附件 cloud_download Prim.java ( 3.33kb, 1次下载 )
eject