为什么Prim算法常规实现需要距离数组？无距离数组实现是否正确

首先明确你的代码是正确的 #

你实现的是带延迟删除的优先队列版本Prim算法，确实可以正确计算连通图的最小生成树总权值，也可以通过记录前驱指针得到MST结构，这一点没有问题。

你存在的认知偏差 #

• 时间复杂度评估错误：你的实现时间复杂度不是O(VlogV)，而是O(ElogE)。因为每条边都会被无条件推入优先队列，最坏情况下E达到V²量级，此时你的实现复杂度会退化为O(V² logV)，远高于稠密图下最优的O(V²)复杂度。
• 「绝大多数场景性能比Kruskal快」的结论不成立：稀疏图场景下Kruskal的常数开销更低，实现更简单，实际性能往往优于该版本Prim；只有在中等稠密程度的图上，该版本Prim才会有一定性能优势。

距离数组的必要性 #

距离数组dist[]的核心作用是记录「未加入MST的节点到当前MST的最短距离」，主要用于两个核心优化场景：

1. 优先队列入队剪枝
   没有距离数组时，所有邻接未访问节点的边都会被推入优先队列，哪怕该节点已经存在一条权值更小的边在队列中。这些无效边会占用优先队列的存储空间，也会增加弹出操作的无效开销。
   引入距离数组后，每次遍历邻接边时可以先判断：当前边权 < dist[邻接节点]，只有满足该条件时才更新dist并将边推入优先队列，能大幅减少优先队列中的无效元素数量，特别是在稠密图中优化效果极其明显。
2. 适配更高性能的Prim实现
   如果是稠密图场景，我们可以直接放弃优先队列，改用距离数组每次O(V)遍历找未访问节点中dist最小的节点，总时间复杂度为O(V²)，比你当前的实现、以及Kruskal算法的性能都高得多。
   此外理论上最优的Prim实现（配合斐波那契堆），也需要依赖距离数组做松弛操作，才能达到O(E + VlogV)的最优时间复杂度，没有距离数组就无法实现这类优化版本。

内容的提问来源于stack exchange，提问作者GyuMin Han