该用 kruskal 当边少点分散（e ≈ v 或更小），用 prim 当边多点集中（e ≈ v²）；kruskal 依赖 o(e log e) 排序与并查集，prim 邻接矩阵版为 o(v²)，邻接表堆优化版为 o(e log v)。
选 Prim 还是 Kruskal，取决于图的稠密程度和你手头的数据结构——不是看“哪个更经典”，而是看 edge_count 和 vertex_count 的比值是否明显大于或小于 vertex_count。
什么时候该用 Kruskal 算法
边少、点分散，比如社交网络中用户关系稀疏，或地理坐标点之间只连少量邻近边。这时 edge_count ≈ vertex_count 或更小。
-
Kruskal先对所有边排序，时间复杂度主导项是O(e log e)；边少时这步很快 - 必须配合并查集（
union-find）做环检测，别手写数组模拟——容易在路径压缩或按秩合并上出错 - 输入如果是邻接表或边列表，不用转存；但若只有邻接矩阵，得先遍历提取所有非零边，别漏掉
weight == 0的合法边（除非明确约定 0 表示无边） - 排序时若权值重复，
std::sort默认不稳定，但 MST 不依赖顺序，可忽略；如需确定性输出，加三元组比较：先比weight，再比from，最后比to
什么时候该用 Prim 算法
边多、点集中，比如网格图、全连接传感器网络，或邻接矩阵天然存在的场景。edge_count ≈ vertex_count² 时，Prim 更稳。
- 邻接矩阵版
Prim时间复杂度是O(v²)，不依赖边数；邻接表 + 堆优化版是O(e log v)，但常数高、编码易错 - 起始点选谁都行，但别写死为 0 —— 实际数据顶点编号可能从 1 开始，或用字符串 ID，得先映射到 0-based 索引
- 维护
min_dist[v]数组时，初始化要设为INT_MAX或足够大的值，别用 -1 当“未访问”标记，否则和负权边逻辑冲突（虽然 MST 要求权非负，但防御性编码建议统一用极大值） - 更新邻居距离时，检查
graph[u][v] > 0不够——得确认graph[u][v] != INF，否则会把无效边当有效边松弛
Kruskal 实现中最容易崩的三个地方
不是算法逻辑错，而是工程细节翻车：
- 并查集的
find没路径压缩 → 小图看不出，大图（v > 1e4）直接 TLE - 边排序后没去重，但原始数据含重边 →
Kruskal本身能处理，但若去重逻辑写成 “跳过from==to” 就误杀合法重边 - 读入边时把
from和to当无向边处理了，但代码里只存了一次方向 → 后续并查集查find(from)和find(to)没问题，但输出 MST 边时方向反了，调试时看着像环
两个算法输出结果不一致？先盯住这个
MST 不唯一，但总权值必须一致。如果 kruskal_total_weight != prim_total_weight，99% 是以下之一：
- 某处用了
int存权值，但累加溢出（尤其权值大、边数多时），换long long再试 -
Prim中选最小未访问点时，用了min_element但没跳过已访问点，导致选中一个min_dist[v] == INT_MAX的点，后续数组越界 -
Kruskal的边结构体排序函数里，把a.weight 错写成 <code>，导致 <code>std::sort行为未定义，不同 STL 实现结果不同
真正难调的从来不是主干逻辑，而是这些散落在初始化、边界、类型转换里的小缝——它们不会报编译错误，但会让 MST 权值差 1、少一条边、或多一个环。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
