代码随想录算法训练营第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;}
}