最小生成树
给定一个带权无向连通图，选取一棵树，让树所有边上权的总和最小，叫最小生成树N个顶点，一定有N-1条边包含全部顶点N-1条边都要在图中算法介绍
普里姆算法求最小生成树，也就是在包含n个顶点的连通图中，找出只有（n-1）条边所含所有n个顶点的连通子图，也就是所谓的极小连通子图
修路问题：
该乡中有7个村庄（A,B,C,D,E,F,G）各个村庄的距离用边数表示（权）比如 A - B 距离5公里问：如何修路保证各个村庄都能联通，并且保证总的修路里程最短？
代码实现
public class PrimAlgorithmm {public static void main(String[] args) {//看看图是否创建成功char[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length;//邻接矩阵用二维数组表示 10000表示两个点不连通int [][]weight=new int[][]{{10000,5,7,10000,10000,10000,2},{5,10000,10000,9,10000,10000,3},{7,10000,10000,10000,8,10000,10000},{10000,9,10000,10000,10000,4,10000},{10000,10000,8,10000,10000,5,4},{10000,10000,10000,4,5,10000,6},{2,3,10000,10000,4,6,10000},};//创建MGraph对象MGragh gragh = new MGragh(verxs);//创建MinTree对象MinTree minTree = new MinTree();minTree.createGraph(gragh,verxs,data,weight);//输出minTree.showGraph(gragh);//测试普利姆minTree.prim(gragh,0);}}//创建最小生成树class MinTree{//创建图的邻接矩阵/*** @param gragh 图对象* @param verxs 图对应顶点个数* @param date 图的各个顶点值* @param weight 图的矩阵*/public void createGraph(MGragh gragh,int verxs,char date[],int[][] weight){int i,j;for (i=0;i<verxs;i++){gragh.data[i] = date[i];for (j=0;j<verxs;j++){gragh.weight[i][j] = weight[i][j];}}}//显示图片邻接矩阵public void showGraph(MGragh gragh){for (int[] link:gragh.weight){System.out.println(Arrays.toString(link));}}//编写算法得到最小生成树public void prim(MGragh gragh,int v){//visited[] 标记节点被访问过int visited[]=new int[gragh.verxs];//把当前节点标记为visited[v] = 1;//h1和h2记录两个顶点下标int h1 = -1;int h2 = -1;int minWeight = 10000;//先初始化大数 有比他小的就替换for (int k = 1; k < gragh.verxs ; k++){//每次生成的子图和哪个节点的距离最近for (int i=0;i<gragh.verxs;i++){ //i节点表示被访问过的节点for (int j=0;j<gragh.verxs;j++){ //j节点表示还没访问过的节点if (visited[i]==1 && visited[j] ==0 && gragh.weight[i][j] < minWeight){//替换minWeightminWeight = gragh.weight[i][j];h1 = i;h2 = j;}}}System.out.println("边<"+gragh.data[h1]+","+gragh.data[h2]+">权值："+minWeight);//当当前节点标记为已经访问visited[h2] = 1;minWeight = 10000;}}}class MGragh{int verxs; //表示图的节点个数char[] data;//表示节点数据int [][] weight; //存放边 邻接矩阵public MGragh(int verxs){this.verxs = verxs;data = new char[verxs];weight = new int[verxs][verxs];}}
