普里姆算法（Prim算法）:
图论中的一种算法，可在加权连通图里搜索最小生成树。意即由此算法搜索到的边子集所构成的树中，不但包括了连通图里的所有顶点（英语：Vertex (graph theory)），且其所有边的权值之和亦为最小。
普里姆算法和Kruskal算法的区别
两者都是贪心策略追求最优解,但是普里姆算法讲究全局优先,Kruskal算法讲究的是局部优先.
普里姆算法思路
1).输入：一个加权连通图，其中顶点集合为V，边集合为E；
2).初始化：Vnew = {x}，其中x为集合V中的任一节点（起始点），Enew = {},为空；
3).重复下列操作，直到Vnew = V,代表所有顶点都已经连接起来了：
a.在集合E中选取权值最小的边<u, v>，其中**u为集合Vnew中的元素，而v不在Vnew集合当中，**并且v∈V（如果存在有多条满足前述条件即具有相同权值的边，则可任意选取其中之一）；
b.将v加入集合Vnew中，将<u, v>边加入集合Enew中；
4).输出：使用集合Vnew和Enew来描述所得到的最小生成树。
图解:
假设有A,B,C,D,E 5个村庄要修路使每个村子都有路连接(A->B->C也算A,C相连),但是要修路的总长度最小.
1.假设重A村开始选择;
A只有3个选择,即<A,D>=5,<A,C>=7,<A,E>=10,其中A,D之间最短所以选择A,D修路
2.A,D之间修了路后A,D变成了一个整体也有3种选择即<A,C>=7,<A,E>=10,<D,B>=9,所以应该选择路径最短的A,C,这就是普里姆算法体现出来的全局优先
3.A,C之间修了路,A,C,C变成了一个整体,有了4种选择即<A,E>=10,<C,E>=6,<C.B>=12,<D,B>=9,所以应该选<C,E>=6,C,E之间修路
4.C,E之间修路后有3中选择即<C,B>=12,<D,B>=9,<E,B>=4,所以应该在E,B之间修路,这时各个村庄就完全修通了.
完整Java代码实现
package com.yg.algorithm;/*
@author Mu_Mu
@date 2020/3/20 9:50
*/
import javax.validation.constraints.Max;
import javax.xml.crypto.Data;
import java.util.Arrays;
public class PrimAlgorithm {
//表示不能互互通的顶点之间的距离
private static final int MAX = 10000;
public static void main(String[] args) {
char []data={'A','B','C','D','E'};
//构建顶点之间的距离
int [][]weight={{MAX,MAX,7,5,10},{MAX,MAX,12,9,4},
{7,12,MAX,MAX,6},{5,9,MAX,MAX,MAX},{10,4,6,MAX,MAX}};
Graph graph = new Graph(data.length);
MinTree.setGraph(graph, data.length, data, weight);
MinTree.showGraph(graph);
MinTree.minPath(graph,0);
}
}
class MinTree {
//构建图
public static void setGraph(Graph graph, int verxs, char[] data, int[][] weight) {
for (int i = 0; i < verxs; i++) {
graph.data[i]=data[i];
for (int j = 0; j < verxs; j++) {
graph.weight[i][j]=weight[i][j];
}
}
}
//构建最优修路路径
//v代表从哪个顶点开始修
public static void minPath(Graph graph,int v) {
//用于记录哪些顶点已经被选过了
int []visited=new int[graph.verxs];
//表示V被选过了
visited[v]=1;
//表示n个顶点需要n-1条边
for (int i = 1; i < graph.verxs; i++) {
//最小路径
int minPath= 10000;
int h1=-1;//用于记录最小路劲对应的已选择过顶点的下标
int h2=-1;//用于记录最小路劲对应的未选择过顶点的下标
//用来每次选取距离已被选过的边这个集体最近的边,并确定路径
for (int j = 0; j < graph.verxs; j++) {
for (int k = 0; k < graph.verxs; k++) {
if (visited[j]==1 && visited[k]==0 && graph.weight[j][k]<minPath ) {
minPath=graph.weight[j][k];
h1=j;
h2=k;
}
}
}
System.out.println("已选择顶点中" + graph.data[h1] + "与未选择顶点中"
+ graph.data[h2] + "相连权值为" + graph.weight[h1][h2]);
visited[h2]=1;
}
}
//打印图
public static void showGraph(Graph graph) {
for (int[] w : graph.weight) {
System.out.println(Arrays.toString(w));
}
}
}
class Graph {
public int verxs=0;//顶点数
public char []data;//顶点数据
public int [][]weight;//表示图之间的边
public Graph(int verxs) {
this.verxs = verxs;
data=new char[verxs];
weight=new int[verxs][verxs];
}
}