麦客网做网站,建e网室内设计网官网全景图库,用xampp搭建wordpress,海报设计图片手绘图一、算法逻辑
想要轻松形象理解Prime的算法逻辑#xff0c;视频肯定比图文好。
小编看过很多求相关的教学视频#xff0c;这里选出一个我认为最好理解的这一款安利给大家。
因为他不仅讲解细致#xff0c;而且还配合了动画演示#xff0c;可以说把一个抽象的东西讲的非常…一、算法逻辑
想要轻松形象理解Prime的算法逻辑视频肯定比图文好。
小编看过很多求相关的教学视频这里选出一个我认为最好理解的这一款安利给大家。
因为他不仅讲解细致而且还配合了动画演示可以说把一个抽象的东西讲的非常的形象了。
B站链接【图-最小生成树-Prim(普里姆)算法】 接下来小编会对视频中的算法补充一个java的具体实现
二、java实现
只用一个接口写的代码肯定不好理解因为涉及到图的操作所以这里先给一下基本的图的代码使用邻接矩阵 class Constant {public static final int MAXInteger.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;//存的值就是顶点的下标SetInteger setX new HashSet(n);//长度就是所有顶点的大小用来存确定的顶点SetInteger setY new HashSet(n);//用来存还没有确定的顶点setX.add(indexSrc);//起始顶点已经是确定好了的所以直接放到setX这个集合中//接下来把除了起始顶点外的其他顶点都放到setY这个集合中也就是还未确定的顶点for (int i 0; i n; i) {if (i ! indexSrc) setY.add(i);}/** 定义一个优先级队列小根堆因为有得到最小权值用来存储还没有确定好的 从确定顶点到没有确定顶点的边*/PriorityQueueEdge 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}
