prim算法

刚学习prim算法，看了好久，最后还是抄了一遍理解清楚了，现在梳理一下框架

53. 寻宝（第七期模拟笔试） (kamacoder.com)

第一步输入数据，没有路径的地方需要设置成一个大数，类似此路不通的意思。用一个grid二维数组记录下来。

第二步记录每个节点到已生成最小生成树的距离，用一个midDir一维数据记录，初始值每个节点都不连通，设为一个大数；然后用一个isAddTree来记录是否已经加入最小生成树。

然后开始prim三部曲，循环遍历v次，因为要加入v个节点（此时的i无任何意义，只代表循环次数）：

定义min：记录节点到最小生成树的最小距离.初始设为MAX_VALUE，因为第一个节点要加入

定义当前节点curnode：初始值设为-1

        循环每个节点：

        1、if（当前节点没有加入生成树&&比已经记录其他节点到生成树的距离都要小）：

                curnode等于它；

                min等于它到最小生成树的距离；

        2、遍历完后，找到了最小结点，把它加入到最小生成树，isAddTree = true

        3、更新当前结点到最小生成树的距离

                遍历每个结点：

                        if（结点没加入最小生成树&&grid[curnode][j] < midDir）:

                                minDir[j] = grid[curnode][j];

遍历minDir求和得到结果

import java.util.*;public class prim{public static void main (String[] args) {/* code */Scanner sc = new Scanner(System.in);int v = sc.nextInt();int e = sc.nextInt();//c从1号节点开始，更符合习惯int[][] grid = new int[v+1][v+1];for(int i = 0; i<= v; i++){Arrays.fill(grid[i],10001);}for(int i = 0; i < e; i++){int s = sc.nextInt();int t = sc.nextInt();int q = sc.nextInt();grid[s][t] = q;grid[t][s] = q;}//存储每个节点到最小生成树的距离int[] minDir = new int[v+1];Arrays.fill(minDir,10001);//记录哪些节点已经加入生成树boolean[] isAddTree= new boolean[v+1];for(int i = 1; i <= v; i++){//1.选择距离生成树最近的节点int min = Integer.MAX_VALUE;int curNode = -1;for(int j = 1; j <= v; j++){//如果j结点没有加入并且距离最小，记录当前距离，看看是不是最近的，是最近的就加入if(!isAddTree[j] && minDir[j] < min){curNode = j;min = minDir[j];}}//2.将最近的节点加入到最小生成树isAddTree[curNode] = true;//3.更新节点到最小生成树的距离，因为最小生成树已经更新了(实际只需要更新和curNode的最小距离)for(int j = 1; j<=v; j++){if(!isAddTree[j] && grid[curNode][j] < minDir[j]){minDir[j] = grid[curNode][j];//System.out.println(minDir[j]);}}}//统计结果int res = 0;for(int i = 2; i <=v; i++){res += minDir[i];}System.out.println(res);/*/打印邻接矩阵for(int i = 0; i<v+1;i++){for(int j = 0; j<v+1; j++){System.out.print(grid[i][j]+" ");}System.out.println();}//*/}
}