做灯箱的网站,微信公众号编辑,河南双师培训网站,网站接入服务单位实现描述
如图#xff1a;
Prim算法的基本思想是从一个顶点开始#xff0c;逐步构建最小生成树。具体步骤如下#xff1a;
随机选取一个顶点作为起始点#xff0c;并将其加入最小生成树的集合中。从该顶点出发#xff0c;选择一条边连接到其他未被访问的顶点中的最小权…实现描述
如图
Prim算法的基本思想是从一个顶点开始逐步构建最小生成树。具体步骤如下
随机选取一个顶点作为起始点并将其加入最小生成树的集合中。从该顶点出发选择一条边连接到其他未被访问的顶点中的最小权值边。将该顶点加入到最小生成树的集合中并标记为已访问。重复步骤2和步骤3直到最小生成树包含所有顶点。
与Kruskal算法相比Kruskal是选择最小边通过判断连通性加入最小生成树 Prim算法是选择点构成最小生成树然后选择未加入的点通过权重判断是否能加入最小生成树
下面是详细的构建过程
首先加入index0的点此时最小生成树包含了只有0
最小生成树此时节点[0],其他各个节点到最小生成树距离表
索引minDistance所有节点到最小生成树的最小距离nodeInTheTree记录节点是否在最小生成树里面0true15false28false37false4无穷大false53false
之后选择距离最小生成树距离最近的点加入这里选择index5,最小生成树此时节点[0,5],其他各个节点到最小生成树距离表
索引minDistance所有节点到最小生成树的最小距离nodeInTheTree记录节点是否在最小生成树里面0true15false28false36false41false53true
注意此时最小生成树节点[0,5]是两个这两个是一个整体
依次类推直至nodeInTheTree数组里面所有节点都加入然后计算minDistance节点的和即为最小生成树边距离
注意如果需要获取加入的起点-终点的边情况额外添加记录数组parents当获取到本次加入最小生成树的节点时候更新其他点连入最小生成树的边情况进行记录
实现代码
public static void main(String[] args) {int nodeNum 6;int[][] grid {{0, 1, 5},{0, 5, 3},{0, 3, 7},{0, 2, 8},{1, 2, 4},{2, 5, 9},{3, 5, 6},{2, 3, 5},{3, 4, 5},{4, 5, 1}};int[][] matrix new int[nodeNum][nodeNum]; // init matrixfor (int i 0; i nodeNum; i) {Arrays.fill(matrix[i], Integer.MAX_VALUE);}for (int i 0; i grid.length; i) {int u grid[i][0];int v grid[i][1];int w grid[i][2];matrix[u][v] w;matrix[v][u] w;}int[] minDistance new int[nodeNum]; // 所有节点到最小生成树的最小距离Arrays.fill(minDistance, Integer.MAX_VALUE);boolean[] nodeInTheTree new boolean[nodeNum]; //记录节点是否在最小生成树里面int[] parents new int[nodeNum]; //记录最小生成树的边Arrays.fill(parents, -1);for (int i 0; i nodeNum; i) {int current 0; //默认0int minValue Integer.MAX_VALUE;//选择距离当前生成树最近的点for (int j 0; j nodeNum; j) {if (nodeInTheTree[j]) {//在树中跳过continue;}if (minDistance[j] minValue) {current j;minValue minDistance[j];}}nodeInTheTree[current] true;//将选择的节点加入最小生成树//更新其他节点到最小生成树的距离for (int j 0; j nodeNum; j) {if (nodeInTheTree[j]) {//在树中跳过continue;}if (matrix[current][j] minDistance[j]) {minDistance[j] matrix[current][j];parents[j] current; //用最新选择的点去连接之前的点}}}int totalDistance 0;for (int i 1; i nodeNum; i) {totalDistance minDistance[i];}System.out.println(总的权重值为 totalDistance);//输出边for (int i 1; i nodeNum; i) {System.out.println(u i ; v parents[i]);}}
