概念

最小生成树

用最小总权重连通所有顶点：Kruskal 按边排序贪心加边、Prim 按点扩展，Borůvka 算法适合并行，是贪心思想的典范。

阅读路径

参考可汗学院 Get ready 机制：先修概念 → 当前概念 → 进阶概念，✓ 表示已读。

最小生成树图论

01定义

最小生成树用最小总权重连通所有顶点。Kruskal 按边权排序贪心加边（并查集判圈），Prim 从一点出发贪心扩展，Borůvka 多源并行——三者都是贪心思想的最优性典范，正确性由割性质保证。

最小生成树：金边连通所有顶点且总权最小

任一割的最轻跨割边必属于某 MST——Kruskal 与 Prim 的正确性全赖此引理；环性质（圈上最重边可弃）是其对偶。

Kruskal $O(E\log E)$ 配并查集、适合稀疏图；Prim 配二叉堆 $O(E\log V)$ 、斐波那契堆 $O(E+V\log V)$ 、适合稠密图；Borůvka 天然并行。

边权互异则 MST 唯一；「次小生成树」与灵敏度分析只需换一条边——工程备份路线的理论支撑。

\text{MST}:\ \min\sum_{e\in T}w(e)\ \text{s.t.}\ T\ \text{连通无圈}

捷克数学家 Borůvka 1926 年为电网设计发明第一个 MST 算法；Kruskal 1956、Prim 1957 分别独立给出今天通用的两个版本。

通信网与电网的最低成本铺设、聚类分析（单链接聚类即 MST 截断）、图像分割、近似 TSP（2 倍近似以 MST 为骨架）。

Kruskal：按权排序逐步连树每次取最小权边且不成环，直到 n−1 条边

step 已选边数0