给我简单讲Kruskal、Prim以及两者的区别

最小生成树（Minimum Spanning Tree, MST）是图论中的绝对核心考点。两者的终极目标完全一致：在一个包含 $V$ 个顶点的连通无向带权图中，挑出 $V-1$ 条边，使得所有顶点连通且总边权和最小。

它们的区别可以用六个字概括：Kruskal 贪边，Prim 贪点。

一、Kruskal 算法（克鲁斯卡尔 ——“加边法”）

1. 核心思想（全局贪心选边）

先把图里所有边拆下来，按权值从小到大排好队。每次挑一条当前权值最小的边：

• 若加上这条边不会形成环（即边的两个端点原本不连通），就把它收编进生成树；
• 若加上会成环，则直接扔掉；
• 重复此过程，直到选满了 $V-1$ 条边为止。

2. 底层武器：并查集（DSU）

• 如何高效判环？ 用并查集维护连通块。
• 检查一条边的两端点 $u, v$：若 find(u) == find(v)，说明两点早已连通，加上必成环，舍弃；否则 merge(u, v)，计数器加 1。

3. 复杂度

• 边排序需要 $O(E \log E)$，并查集操作近乎 $O(1)$。
• 总时间复杂度：$O(E \log E)$（即 $O(E \log V)$），仅与边数 $E$ 强相关。

二、Prim 算法（普里姆 ——“加点法”）

1. 核心思想（滚雪球扩充点集）

从任意一个起点开始，维护一个**“已经在树里的点集 $S$”**：

1. 初始时，集合 $S$ 只有起点 1 个点；
2. 每次在“尚未入树的所有点”中，寻找一个距离集合 $S$ 最近的点（即连接已选点集与未选点集的权重最小的边）；
3. 把该点加入 $S$，并用它的所有出边更新其它未入树点到 $S$ 的最短距离；
4. 重复此过程，直到所有 $V$ 个点都被收进 $S$。

灵感直通车：Prim 的扩张过程和单源最短路 Dijkstra 算法几乎完全一致！唯一区别是更新数组的定义：Dijkstra 存的是“到起点的累加距离”，Prim 存的是“到当前生成树点集的单边最近距离”。

2. 复杂度

• 朴素 Prim（基于邻接矩阵 + 暴力循环）：$O(V^2)$，与边数无关。
• 堆优化 Prim（基于邻接表 + 优先队列）：$O(E \log V)$。

三、两者的核心区别与做题选型对照表

四、考场决断指南（3 秒决定用谁）

1. 看数据规模（选型黄金法则）：

   • 给出点数 $V \le 1000$，边数 $E$ 很大（完全图或接近稠密图）：选 朴素 Prim（稳过 $O(V^2)$，完全不用建几百万条边）。
   • 给出点数 $V \le 10^5$，边数 $E \le 2 \times 10^5$（常规稀疏网格/公路网）：闭眼写 Kruskal，排序+并查集又快又绝不易写挂。

2. 考场特例辨析题（概念常考坑点）：

   • 所有边权均不同时：图的最小生成树唯一（此时 Kruskal 和 Prim 算出的生成树结构完全相同）。
   • 边权有重复时：最小生成树可能不唯一，但最小边权和必定唯一。
   • 负权边：Kruskal 和 Prim 完全支持负权边（这与求最短路的 Dijkstra 截然不同！因为 MST 只追求边的相对大小，不依赖“非递减距离和”的贪心条件）。