选型与应用场景
基于通用算法套路 · 核于 2026-07
速查
- 选型第一准则：看图的稀疏程度——稀疏图（E ≪ V²）选 Kruskal（排序代价小），稠密图（E ≈ V²）选 Prim 朴素 O(V²)（避开 log 因子，常数极小）。
- Kruskal 何时占优：E 较小（如 E = O(V)），O(E log E) 远小于 O(V²)，且天然用边集数组（输入就是边列表），省去建图。
- Prim 何时占优：E 接近 V²（如完全图 V(V−1)/2 条边），堆优化 O(E log V) ≈ O(V² log V) 反而比朴素 O(V²) 慢——此时邻接矩阵朴素版最优，常数小且不依赖 E。
- 图不连通怎么办：没有生成树，只能求最小生成森林（每个连通分量一棵 MST）；Kruskal 自然得到（选不满 n−1 条停），Prim 需对每个未访问分量重启。
- MST 唯一性：边权全互异时 MST 唯一；存在相等权值时可能有多棵总权相同的 MST——判唯一性看「同权边是否构成可替代的环」。
- Kruskal 与 Prim 结果关系：两者都能得到 MST；权唯一时边集合相同，权有相等时边集合可能不同但总权值必然相同。
- 应用领域：①网络设计（光缆/电网/管道连通，最低成本）；②聚类（删掉 MST 中最大的 k−1 条边得 k 个簇）；③近似 TSP（MST 权 ≤ 最优 TSP，作为下界/近似解）；④图像分割（基于像素相似度的 MST）。
- 避坑：无向图边要双向处理（邻接表/Kruskal 边表别漏）；Kruskal 别忘
find判同根；Prim 堆要跳过已选顶点；输入可能含重边/自环（Kruskal 自然处理，Prim 取最小权边）。 - 复杂度公式：Kruskal O(E log E)；Prim 堆 O(E log V)，Prim 矩阵朴素 O(V²)。
一、稀疏 vs 稠密：选型的核心
MST 选型本质是一道关于 E 与 V² 大小关系的算术题。三种主流实现的复杂度：
| 实现 | 复杂度 | 何时最优 |
|---|---|---|
| Kruskal | O(E log E) | E 小（稀疏图） |
| Prim 堆优化 | O(E log V) | 中等稠密度 / 通用 |
| Prim 邻接矩阵朴素 | O(V²) | E 接近 V²（稠密图） |
判断逻辑：
- 稀疏图（E ≪ V²，典型 E = O(V)）：Kruskal 的 O(E log E) 极小（如 E = V，则 O(V log V)）；Prim 矩阵朴素 O(V²) 浪费（要扫大量不存在的边）。选 Kruskal。此时 Kruskal 还有个隐性优势——边集数组就是输入本身，不用先建邻接表。
- 稠密图（E ≈ V²，典型完全图 E = V(V−1)/2）：Prim 堆优化 O(E log V) ≈ O(V² log V)，反而比朴素 O(V²) 多一个 log 因子；而朴素版每轮 O(V) 扫描找最小，常数极小、不依赖 E。选 Prim 矩阵朴素。
- 中等稠密度 / 不确定：Prim 堆优化 O(E log V) 是通用兜底；竞赛里 Kruskal 因代码短也常被无脑套用。
记忆口诀：「边少选 Kruskal（排序省事），边多选 Prim（矩阵朴素稳）」。
二、图不连通：最小生成森林
MST 的前提是图连通。若图有多个连通分量，求不出「一」棵覆盖所有顶点的生成树，只能求最小生成森林——每个连通分量各一棵 MST。
- Kruskal：天然得到森林——扫完所有边后若选中数
cnt < n−1，说明有n − 1 − cnt个分量没连起来，已选的边就是森林（每个分量内部是它的 MST）。 - Prim：需要对每个未访问的顶点重新启动一次（外层套一个
for检测未访问分量），各次结果累加。
判连通性可以前置（DFS/BFS/并查集数连通分量），也可以直接在 MST 算法里靠 cnt < n−1 检测。
三、MST 的唯一性
一个图的 MST 可能不唯一：
- 边权全互异（无两条边权相等）：MST 唯一。Kruskal 和 Prim 得到的边集合完全一致。
- 存在相等权值：可能有多棵总权相同的 MST。例如一个三角形三边权都是 1，任选两条都是 MST，共 3 种。
判唯一性的方法（面试常考）：
- 充分必要条件：MST 唯一 ⟺ 对任意一个权值，把该权值的所有边同时加入 MST 候选时，它们在 MST 中「应有的位置」不构成可替代的环。
- 实用判法：先求出一棵 MST，再检查每条非树边——若它加入后形成的环上存在与它权值相等的边，则 MST 不唯一（可替换）。
注意：即便 MST 不唯一，所有 MST 的总权值必然相同（否则「最小」就矛盾了）。
四、应用场景
MST 不只是竞赛题，它在工程上有大量真实应用：
1. 网络设计（最经典）
「用最低成本把一群节点连通」——这是 MST 的直接模型：
- 城市间架通信光缆 / 输电网 / 自来水管，每条线路造价不同，求连通所有城市且总造价最低 → MST。
- 电路板布线、PCB 走线、芯片引脚互连的最小成本方案。
- 给村庄通水通电通路、传感器网络（无线传感网把数据汇聚）。
2. 聚类（Single-Linkage 层次聚类）
MST 可用于聚类：先对所有点构建完全图（边权 = 两点距离），求 MST，然后删掉 MST 中权最大的 k−1 条边，剩下的森林就是 k 个簇。这种「单链接层次聚类」简单高效，对噪声敏感是其缺点（链式效应）。
3. 近似旅行商问题（TSP）
TSP（旅行商，求访问所有城市的最短回路）是 NP-hard，但 MST 给出了一个下界和近似解：
- 下界：最优 TSP 回路长度 ≥ MST 权（删掉 TSP 回路任一条边就是一棵生成树，权 ≥ MST 权）。
- 2-近似：对 MST 做 DFS 先序遍历得到的回路长度 ≤ 2 × 最优 TSP（满足三角不等式时）。
4. 图像分割
把图像每个像素当顶点、相邻像素相似度的倒数当边权，求 MST 后按阈值切断大权边，可实现对图像的区域分割。
五、选型决策清单
按以下顺序决策：
- 图连通吗？不连通 → 求最小生成森林（每个分量一棵）。
- 图是稀疏还是稠密？稀疏（E ≪ V²）→ Kruskal；稠密（E ≈ V²）→ Prim 矩阵朴素。
- 输入是什么形式？边列表 → Kruskal 天然契合；邻接矩阵 → Prim 朴素；邻接表 → 任选（Kruskal 更短）。
- 代码量敏感（竞赛/面试手写）？Kruskal 更短（排序 + 并查集）。
- 问唯一性？边权全互异则唯一；否则检查非树边是否与环上等权边可替代。
交互演示
- Kruskal 可视化演示 —— 边按权排序逐条加入，并查集判环
- Prim 可视化演示 —— 从一点出发，堆选最小连边
下一步
理解了选型与应用后，下一步是查阅代码模板、复杂度表与易错点清单做收尾——速查速用，见参考。