Prime算法构造最小生成树（加点法）

一、算法逻辑

想要轻松形象理解Prime的算法逻辑，视频肯定比图文好。

小编看过很多求相关的教学视频，这里选出一个我认为最好理解的这一款安利给大家。

因为他不仅讲解细致，而且还配合了动画演示，可以说把一个抽象的东西讲的非常的形象了。

B站链接：【图-最小生成树-Prim(普里姆)算法】

---

接下来，小编会对视频中的算法补充一个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];//顶点的个数是sizematrix = 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;elsereturn -1;//没有找到，返回-1}