稠密图的Prim算法线性时间实现与研究

提出了改进的Prim算法,能够把■一类稠密图的时间复杂性从■减少到■。算法的基本思想是用最小堆数据结构来保持边界顶点集Y中的顶点,使得Y集中离V-Y集最近的顶点y可以在■时间内被选出。改进后的算法,使得在稠密图的情况下,它的运行时间可以被改善为边数的线性函数,即■。