C++实现最小生成树算法 _ Prim与Kruskal算法对比【源码】

选 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 < b.weight 错写成 a.weight <= b.weight，导致 std::sort 行为未定义，不同 STL 实现结果不同

真正难调的从来不是主干逻辑，而是这些散落在初始化、边界、类型转换里的小缝——它们不会报编译错误，但会让 MST 权值差 1、少一条边、或多一个环。