Prim(普利姆算法)
学习视频
尚硅谷数据结构与算法
普利姆算法是为解决最小生成树问题的一种算法，最小生成树（Minimum Cost Spanning Tree），简称MST，给定一个带权的无向连通图，选取一颗树使树上所有边的权值之后最小，通俗来讲就是在n个节点的无向连通图中找出一个包含n个节点的最小连通子图，且子图没有回路。
算法流程
设G=（V,E）是连通图，T=（U,D）是最小生成树，V,U是顶点集合，E,D是边集合。若从顶点v开始构造最小生成树，将顶点v从集合V中取出放入集合U，设置vistited[v] = 1。若集合U中顶点ui与集合V-U（V-U表示为集合V与集合U的差集）中顶点vj存在边，则寻找这些边的最小值，将最小值边的顶点vj加入集合U，设置visitited[vj] = 1，将最小边加入集合D。重复3步骤知道集合V与集合G相等，此时所有点都被标记过，且边为n-1条。Prim算法解决修路问题
修路问题
算法代码
package Algorithm.primAlgorithm;public class PrimAlgorithm {Graph graph;public PrimAlgorithm(int[][] weight, int vertex, char[] data) {graph = new Graph(vertex);graph.weight = weight;graph.data = data;}public void prim(int v) {//初始化visited数组int[] visited = new int[graph.vertex];//标记卡死节点visited[v] = 1;int m = -1, n = -1;//10000，表示不连通int minWeight = 10000;for (int k = 1; k < graph.vertex; k++) {for (int i = 0; i < graph.vertex; i++) {for (int j = 0; j < graph.vertex; j++) {//重点理解代码if (visited[i] == 1 && visited[j] == 0 && graph.weight[i][j] < minWeight) {minWeight = graph.weight[i][j];m = i;n = j;}}}System.out.println(graph.data[m] + "," + graph.data[n] + "权值：" + minWeight);minWeight = 10000;visited[n] = 1;}}}//定义一个图的内部类class Graph {int vertex;//顶点数char[] data;//顶点集合int[][] weight;//邻接矩阵public Graph(int vertex) {this.vertex = vertex;data = new char[vertex];weight = new int[vertex][vertex];}}
测试代码：
public class Client {public static void main(String[] args) {char[] data = new char[]{'A','B','C','D','E','F','G'};int vertex = data.length;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}};PrimAlgorithm primAlgorithm = new PrimAlgorithm(weight, vertex, data);primAlgorithm.prim(0);}}
