一、算法逻辑
想要轻松形象理解Prime的算法逻辑，视频肯定比图文好。
小编看过很多求相关的教学视频，这里选出一个我认为最好理解的这一款安利给大家。
因为他不仅讲解细致，而且还配合了动画演示，可以说把一个抽象的东西讲的非常的形象了。
接下来，小编会对视频中的算法补充一个java的具体实现
二、java实现
只用一个接口，写的代码，肯定不好理解，因为涉及到图的操作，所以这里先给一下基本的图的代码（使用邻接矩阵）：
class Constant {
public static final int MAX=Integer.MAX_VALUE;
}
public class GraphByMatrix {
private char[] arrayV;//顶点数组
private int[][] matrix;//矩阵，存放每一个边的权重
private boolean isDirect;//是否是有向图
/**
* 构造方法
*
* @param size 代表当前顶点的个数
* @param isDirect 是否是有向图，true是有向图
*/
public GraphByMatrix(int size, boolean isDirect) {
this.arrayV = new char[size];//顶点的个数是size
matrix = new int[size][size];
for (int i = 0; i < size; i++) {
Arrays.fill(matrix[i], Constant.MAX);
}
this.isDirect = isDirect;
}
/**
* @param srcV 起点
* @param destV 终点
* @param weight 权值
*/
public void addEdge(char srcV, char destV, int weight) {//重载之一，用来建立普通图
int srcIndex = getIndexOfV(srcV);
int destIndex = getIndexOfV(destV);
matrix[srcIndex][destIndex] = weight;
//如果是无向图 那么相反的位置 也同样需要置为空
if (!isDirect) {
matrix[destIndex][srcIndex] = weight;
}
}
/**
* @param srcIndex 起点
* @param desIndex 终点
* @param weight 权重
*/
public void addEdge(int srcIndex, int desIndex, int weight) {//重载两个之一，用来建立最小生成树
matrix[srcIndex][desIndex] = weight;
//如果是无向图 那么相反的位置 也同样需要置为空
if (!isDirect) {
matrix[desIndex][srcIndex] = weight;
}
}
/**
* 获取顶点V的下标
*
* @param v
* @return
*/
private int getIndexOfV(char v) {
for (int i = 0; i < arrayV.length; i++) {
if (arrayV[i] == v) {
return i;
}
}
return -1;
}
/**
* 定义了一个边的抽象类
* 用来存储边的
*/
static class Edge {
public int srcIndex;
public int destIndex;
public int weight;//权重
public Edge(int srcIndex, int destIndex, int weight) {
this.srcIndex = srcIndex;
this.destIndex = destIndex;
this.weight = weight;
}
}
public static void main(String[] args) {
}
}了解了上面的代码，看这个普利姆算法的接口就容易了：
/**
* 普利姆算法
* 最小生成树
*
* @param minTree 要生成的树
* @param V 选择的一个顶点
*/
public int prim(GraphByMatrix minTree, char V) {//需要先给一个顶点，作为起点
int indexSrc = getIndexOfV(V);//获取起始顶点的下标
/*
* 把顶点分成两个集合
* 第一个集合存储已经确定好是minTree的一个顶点
* 第二个存储还未确定的顶点
*
* */
int n = arrayV.length;
//存的值，就是顶点的下标
Set<Integer> setX = new HashSet<>(n);//长度就是所有顶点的大小，用来存确定的顶点
Set<Integer> setY = new HashSet<>(n);//用来存还没有确定的顶点
setX.add(indexSrc);//起始顶点已经是确定好了的，所以直接放到setX这个集合中
//接下来，把除了起始顶点外的其他顶点都放到setY这个集合中（也就是还未确定的顶点）
for (int i = 0; i < n; i++) {
if (i != indexSrc) setY.add(i);
}
/*
* 定义一个优先级队列（小根堆，因为有得到最小权值），用来存储还没有确定好的 从确定顶点到没有确定顶点的边*/
PriorityQueue<Edge> minHeap = new PriorityQueue<>((o1, o2) -> o1.weight - o2.weight);//默认是建立小根堆(因为是自定义类型，要重写compareTo)
//接下来把从起始顶点 连接 到其他顶点的边都放到优先级队列中
for (int i = 0; i < n; i++) {
if (matrix[indexSrc][i] != Constant.MAX) {//从起始顶点->另一个没有确定的顶点存在（等于MAX代表不存在）,就放到队列
minHeap.offer(new Edge(indexSrc, i, matrix[indexSrc][i]));
}
}
int totalWeight = 0;//用来记录总的权值
int edgeN = 0;//用来记录已经确定的边
while (edgeN != n - 1 && !minHeap.isEmpty()) {//只要没有加边到最小生成树，并且队列没有空，就一直加边
//出队一个元素
Edge edge = minHeap.poll();
//判断这个边的 目标顶点 是否 在setX（已经确定的顶点）中
if (!setX.contains(edge.destIndex)) {//如果不在，那么把这个边，放到最小生成树中
//放到最小生成树
minTree.addEdge(edge.srcIndex, edge.destIndex, edge.weight);
//放完一个边，就记得edgeN++ 更新权重
edgeN++;
totalWeight += edge.weight;
//记住把对应的顶点确定
setX.add(edge.destIndex);
//同时，在setY中删除对应目标顶点
setY.remove(edge.destIndex);
/*
* 到了这里，因为已经确定了一个新的顶点，
* 因此，还要在这个新的顶点的基础上，
* 入队从新顶点指向其他顶点的边
* */
for (int i = 0; i < n; i++) {
if (matrix[edge.destIndex][i] != Constant.MAX && !setX.contains(i)) {//只要有边，并且不会形成环，那么入队
minHeap.offer(new Edge(edge.destIndex, i, matrix[edge.destIndex][i]));
}
}
}/*else{
如果在setY就不做操作，如果继续放到minTree中，会形成环！！！
}*/
}
if (edgeN == n - 1)
return totalWeight;
else
return -1;//没有找到，返回-1
}