代码随想录Day57：图论（寻宝prim算法精讲kruskal算法精讲）

kruskal算法精讲

53. 寻宝（第七期模拟笔试）

kruscal的思路：

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

将图中的边按照权值有小到大排序，这样从贪心的角度来说，优先选 权值小的边加入到 最小生成树中。排序后的边顺序为[(1,2) (4,5) (1,3) (2,6) (3,4) (6,7) (5,7) (1,5) (3,2) (2,4) (5,6)]权值相同，前后顺序任意

选边(5,7)，节点5 和 节点7 在同一个集合，不做计算。选边(1,5)，两个节点在同一个集合，不做计算。后面遍历 边(3,2)，(2,4)，(5,6) 同理，都因两个节点已经在同一集合，不做计算。此时 我们就已经生成了一个最小生成树如上图。

在代码中，如果将两个节点加入同一个集合，又如何判断两个节点是否在同一个集合呢？就是我们之前学习的并查集

二、两种算法的区别

        Kruskal 与 prim 的关键区别在于，prim维护的是节点的集合，而 Kruskal 维护的是边的集合。 如果 一个图中，节点多，但边相对较少，那么使用Kruskal 更优。

        一个图里怎么可能节点多，边却少呢？节点未必一定要连着边那， 例如 这个图，大家能明显感受到边没有那么多对吧，但节点数量 和 上述我们讲的例子是一样的。

        为什么边少的话，使用 Kruskal 更优呢？因为 Kruskal 是对边进行排序的后 进行操作是否加入到最小生成树。边如果少，那么遍历操作的次数就少。在节点数量固定的情况下，图中的边越少，Kruskal 需要遍历的边也就越少。而 prim 算法是对节点进行操作的，节点数量越少，prim算法效率就越优。

        所以在 稀疏图中，用Kruskal更优。 在稠密图中，用prim算法更优。

边数量较少为稀疏图，接近或等于完全图（所有节点皆相连）为稠密图

        Prim 算法 时间复杂度为 O(n^2)，其中 n 为节点数量，它的运行效率和图中边树无关，适用稠密图。Kruskal算法 时间复杂度 为 nlogn，其中n 为边的数量，适用稀疏图。

import java.util.*;// 定义一条边：起点、终点、权重
class Edge {int from, to, weight;Edge(int from, int to, int weight) {this.from = from;this.to = to;this.weight = weight;}
}public class Main {// 并查集数组：记录每个节点的“老大”private static int[] parent = new int[10001];// 并查集初始化：每个节点自己是自己的老大public static void initUnionFind() {for (int i = 0; i < 10001; i++) {parent[i] = i;}}// 查找 x 的根节点（路径压缩优化）public static int findRoot(int x) {if (x == parent[x]) return x;return parent[x] = findRoot(parent[x]); // 路径压缩}// 合并两个集合public static void union(int x, int y) {int rootX = findRoot(x);int rootY = findRoot(y);if (rootX == rootY) return; // 已在同一集合parent[rootY] = rootX; // 把 y 的根挂到 x 的根上}public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int V = scanner.nextInt(); // 顶点数int E = scanner.nextInt(); // 边数List<Edge> edges = new ArrayList<>(); // 存所有边int totalCost = 0; // 最小总距离// 读入每条边for (int i = 0; i < E; i++) {int v1 = scanner.nextInt();int v2 = scanner.nextInt();int w = scanner.nextInt();edges.add(new Edge(v1, v2, w));}// 按边的长度从小到大排序（贪心策略）edges.sort(Comparator.comparingInt(e -> e.weight));// 初始化并查集initUnionFind();// 遍历每条边（从最短的开始）for (Edge e : edges) {int root1 = findRoot(e.from);int root2 = findRoot(e.to);// 如果两个点还不连通，就加上这条边if (root1 != root2) {totalCost += e.weight; // 累加这条边的长度union(e.from, e.to);   // 把这两个点连起来}// 如果已经连通了，跳过（避免成环）}System.out.println(totalCost); // 输出最小总长度scanner.close();}
}