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

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