最小生成树Prim算法两种实现的时间复杂度优劣疑问

你提到的推导逻辑本身没有问题：当E达到O(V²)的最坏稠密图场景时，二叉堆+邻接表版本的Prim算法渐进复杂度为O(V²logV)，从纯渐进上界的角度看确实劣于邻接矩阵版本的O(V²)。大家普遍认为前者更优，是结合实际使用场景和综合开销得到的结论，核心原因如下：

• 绝大多数场景下处理的都是稀疏图：日常工程、算法竞赛中遇到的图结构（比如路网、社交网络、调度拓扑、电路连接图等）基本都是稀疏的，E的规模通常为O(V)或O(VlogV)，远小于V²。这种场景下二叉堆版本的时间复杂度约为O(VlogV)，当V超过1000时性能就会明显优于O(V²)的邻接矩阵版本，V越大性能差距越显著。
• 空间开销的差异巨大：邻接矩阵实现需要固定占用O(V²)的存储空间，当V为10^{4时，仅存储邻接矩阵就需要至少400MB（按每个边权占4字节计算），V达到10}5时存储空间会超过40GB，完全无法实现。而邻接表仅需要O(E)的存储空间，哪怕是处理稠密图，空间灵活性也远高于邻接矩阵。
• 实现的普适性更强：实际使用中我们可以根据图的稠密程度动态切换实现，不需要强制用二叉堆版本处理完全稠密图。而二叉堆版本对稀疏、中等稠密的图都有不错的表现，覆盖的场景远多于邻接矩阵版本。

补充说明：如果采用斐波那契堆实现优先队列，Prim算法的时间复杂度可以优化到O(E + VlogV)，哪怕在稠密图场景下也和邻接矩阵版本的O(V²)持平，只是斐波那契堆工程实现复杂度太高，所以工业界很少使用。

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