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

作　　者：徐翠霞[1] 胥宗辉 

机构地区：[1]潍坊学院计算机工程学院,山东潍坊261061 [2]山东科技大学计算科学与工程学院,山东黄岛266590

出　　处：《潍坊学院学报》2023年第5期14-17,92,共5页Journal of Weifang University

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

关 键 词：最小耗费生成树 时间复杂度 稠密图 堆 

分 类 号：TP751[自动化与计算机技术—检测技术与自动化装置]