最小耗费生成树剔除算法及其正确性证明

文章提出了一种新的最小耗费生成树的算法 ,并对其正确性进行了证明。该算法通过从原图中逐步剔除边来形成生成树 ,特别适用于当原图中边数较少 (相对于顶点数 ) 。

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

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