代码随想录算法训练营第57天|卡码网 53. 寻宝 prim算法精讲和kruskal算法精讲

1. prim算法精讲

题目链接：https://kamacoder.com/problempage.php?pid=1053
文章链接：https://www.programmercarl.com/kamacoder/0053.寻宝-prim.html

在这里插入图片描述
prim算法是从节点的角度采用贪心的策略每次寻找距离最小生成树最近的节点并加入到最小生成树中。
prim算法核心就是三步：
1.第一步，选距离最小生成树最近节点
2.第二步，最近节点加入生成树
3.第三步，更新非生成树节点到生成树的距离（即更新minDist数组）
其中：minDist数组用来记录每一个节点距离最小生成树的最近距离。

import java.util.*;public class Main {// prim算法public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int v = scanner.nextInt();int e = scanner.nextInt();// 初始化邻接矩阵，所有值初始化为一个大值，表示无穷大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 x = scanner.nextInt();int y = scanner.nextInt();int k = scanner.nextInt();grid[x][y] = k; // 注意这里对于x和y的不同顺序都设置了值grid[y][x] = k;}// 所有节点到最小生成树的最小距离int[] minDist = new int[v + 1];Arrays.fill(minDist, 10001);int[] parent = new int[v + 1]; // 记录最小生成树的边// 记录节点是否在树里boolean[] isInTree = new boolean[v + 1];// Prim算法主循环for (int i = 1; i < v; i++) { // 注意这里的i的范围int cur = -1;int minVal = Integer.MAX_VALUE;// 选择距离生成树最近的节点for (int j = 1; j <= v; j++) {if (!isInTree[j] && minDist[j] < minVal) {minVal = minDist[j];cur = j;}}// 将最近的节点加入生成树isInTree[cur] = true;// 更新非生成树节点到生成树的距离for (int j = 1; j <= v; j++) {if (!isInTree[j] && grid[cur][j] < minDist[j]) {minDist[j] = grid[cur][j];parent[j] = cur; // 更新当前节点最新的边}}}// 统计结果int result = 0;// 不计第一个顶点，因为统计的是边的权值，v个节点有 v-1条边for (int i = 2; i <= v; i++) { // 注意这里的开头result += minDist[i];}System.out.println(result);scanner.close();}
}

2. kruskal算法精讲

题目链接：https://kamacoder.com/problempage.php?pid=1053
文章链接：https://www.programmercarl.com/kamacoder/0053.寻宝-Kruskal.html

在这里插入图片描述

kruscal的思路：

边的权值排序，因为要优先选最小的边加入到生成树里
遍历排序后的边
如果边首尾的两个节点在同一个集合，说明如果连上这条边图中会出现环
如果边首尾的两个节点不在同一个集合，加入到最小生成树，并把两个节点加入同一个集合

如下这个图来举例。
在这里插入图片描述

将图中的边按照权值有小到大排序。
这样从贪心的角度来说，优先选权值小的边加入到最小生成树中。
排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]
(1,2) 表示节点1 与节点2 之间的边。权值相同的边，先后顺序无所谓。
开始从头遍历排序后的边。
检查每条边的首尾节点是否在同一个集合中：
若是，则说明两个节点之前添加过，因此不添加到最小生成树中；
若否，则添加到最小生成树中，同时添加到同一集合中。

import java.util.*;public class Main {// kruskal算法static int[] father;public static void main(String[] args) {Scanner sc = new Scanner(System.in);int v = sc.nextInt(); // 顶点个数int e = sc.nextInt(); // 边数father = new int[v+1];init();List<Edge> list = new ArrayList<>();for (int i=0;i<e;i++) {int x = sc.nextInt();int y = sc.nextInt();int edge = sc.nextInt();Edge edgeObject = new Edge(x,y,edge);list.add(edgeObject);}// 1. 将边按照升序排列Collections.sort(list,(Edge edge1,Edge edge2)->{return edge1.edge < edge2.edge?-1:(edge1.edge == edge2.edge?0:1);});// 2. 分析每一条边int res=0;List<Edge> resList = new ArrayList<>(); // 保存最小生成树的边for (int i=0;i<list.size();i++) {int x = list.get(i).x;int y = list.get(i).y;int edge = list.get(i).edge;if (isSame(x,y)) { // 检查是否在同一个集合continue;}join(x,y);res += edge;resList.add(list.get(i)); // 保存当前边}System.out.println(res);}public static void join (int u,int v) {u = find(u);v = find(v);if (u == v) return;father[v] = u;}public static int find (int u) {if (u == father[u]) return u;return father[u] = find(father[u]);}public static void init () {for (int i=0;i<father.length;i++) {father[i] = i;}}public static boolean isSame (int u,int v) {u = find(u);v = find(v);return u == v;}
}class Edge {int x;int y;int edge;public Edge(int x,int y,int edge) {this.x = x;this.y = y;this.edge = edge;}
}