1、普利姆算法就是求出最小生成树的算法之一，
2、最小生成树：给定一个带权的无向连接图如何选取一颗生成树，使树上的所有边上权的总和为最小，这就叫做最小生成树。
3、代码：
// 创建一个图的所有元素。class MGraph{int verxs; // 表示图的节点的个数char[] data; // 表示节点的数据int[][] weight; // 存放边，public MGraph(int verxs){this.verxs = verxs;data = new char[verxs];weight = new int[verxs][verxs];}}
// 创建最小生成树class MinTree{// 创建图public void createGraph(MGraph graph, int verxs, char[] data, int[][] weight){int i,j;for(i = 0; i < verxs; i++){// 定点graph.data[i] = data[i];for(j = 0; j < verxs; j++){graph.weight[i][j] = weight[i][j];}}}public void showGraph(MGraph graph){for (int[] link : graph.weight){System.out.println(Arrays.toString(link));}}//prim算法的步骤/***** @param graph 图* @param v 开始的定点的位置*/public void prim(MGraph graph,int v){// 记录已经访问过的节点int[] visited = new int[graph.verxs];// 把当前的节点标记为已经访问过的visited[v] = 1;// h1,h2记录两个定点的下标int h1 = -1;int h2 = -1;int minWeight = 9999;for (int k = 1; k < graph.verxs; k++) {// 因为有graph.verxs顶点，普利姆算法结束后，会有verxs-1条边。// 得出最小的1条边。for (int i = 0; i < graph.verxs; i++) {for (int j = 0; j < graph.verxs; j++) {// prim的核心代码：if(visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight){minWeight = graph.weight[i][j];h1 = i;h2 = j;}}}//找到最小的那条边System.out.println("边<" + graph.data[h1] + "," + graph.data[h2] + "> 权值：" + minWeight);visited[h2] = 1;minWeight = 9999;}}}
public class PrimAlgorithm {public static void main(String[] args) {// 测试图是否创建okchar[] data = new char[]{'A','B','C','D','E','F','G'};int verxs = data.length; // 获取顶点的长度// 邻接矩阵的关系使用二维数组表示int[][] weight = new int[][]{{9999,5,7,9999,9999,9999,2},{5,9999,9999,9,9999,9999,3},{7,9999,9999,9999,8,9999,9999},{9999,9,9999,9999,9999,4,9999},{9999,9999,8,9999,9999,5,4},{9999,9999,9999,4,5,9999,6},{2,3,9999,9999,4,6,9999},};MGraph graph = new MGraph(verxs);// 创建MinTree的对象MinTree minTree = new MinTree();minTree.createGraph(graph,verxs,data,weight);minTree.showGraph(graph);// 测试普利姆算法minTree.prim(graph,2);}}
