1、最小生成树
把一个带权连通图的生成树中边的权之和定义为树权，在所有生成树中，树权最小的生成树称为最小生成树
2、Prim算法实现
将顶点分为两部分，即U和V-U，U中的顶点是当前为止最小生成树中的顶点，V-U是尚未处理过的顶点集，选这两个顶点集之间的所有边作为候选边，每次从中选取一条权值最小边作为最小生成树的一条边，然后调整U、V-U、及两个顶点集的侯选边。
以下代码仅供参考
以下代码仅供参考
以下代码仅供参考
/** *作者：魏宝航 *2020年11月23日,下午13:43 */ import org.omg.CORBA.INTERNAL; import java.io.IOException; import java.util.Scanner; public class MatrixUDG { private char[] mVexs; private int[][] mMatrix; private int num; public MatrixUDG(char[] vexs, char[][] edges) { num = vexs.length; mVexs = new char[num]; for (int i = 0; i < mVexs.length; i++) mVexs[i] = vexs[i]; mMatrix = new int[num][num]; for(int i=0;i<num;i++){ for(int j=0;j<num;j++){ if(edges[i][j]=='∞'){ mMatrix[i][j]=Integer.MAX_VALUE; }else{ mMatrix[i][j]=Integer.parseInt(edges[i][j]+""); } } } } public void print() { System.out.printf("Martix Graph:\n"); for (int i = 0; i < mVexs.length; i++) { for (int j = 0; j < mVexs.length; j++){ if(mMatrix[i][j]<Integer.MAX_VALUE){ System.out.printf("%d ", mMatrix[i][j]); }else{ System.out.print("∞ "); } } System.out.printf("\n"); } } public void Prim(int v){ int[] lowcost=new int[1000]; int[] closest=new int[1000]; int min=Integer.MAX_VALUE; int k=0; for(int i=0;i<this.num;i++){ lowcost[i]=this.mMatrix[v][i]; closest[i]=v; } for(int i=1;i<this.num;i++){ min=Integer.MAX_VALUE; for(int j=0;j<this.num;j++){ if(lowcost[j]!=0&&lowcost[j]<min){ min=lowcost[j]; k=j; } } System.out.printf("边(%d,%d)权为：%d\n",closest[k],k,min); lowcost[k]=0; for(int j=0;j<this.num;j++){ if(this.mMatrix[k][j]!=0&&this.mMatrix[k][j]<lowcost[j]){ lowcost[j]=this.mMatrix[k][j]; closest[j]=k; } } } } public static void main(String[] args) { char[] vexs={'0','1','2','3','4','5'}; char[][] edges=new char[][]{ {'0','6','1','5','∞','∞'}, {'6','0','5','∞','3','∞'}, {'1','5','0','5','6','4'}, {'5','∞','5','0','∞','2'}, {'∞','3','6','∞','0','6'}, {'∞','∞','4','2','6','0'}, }; MatrixUDG g=new MatrixUDG(vexs,edges); g.print(); g.Prim(0); } }
