基于Prim算法的最小生成树优化研究

• 作者: 张黎 江波
• 来源期刊: 计算机工程与设计
• 学科: 工学
• 关键词: Prim算法 最小生成树 无向图 邻接矩阵 邻接多重表
• 年，卷（期）: 2009,（13）
• 所属期刊栏目: 开发与应用
• 页码范围: 3244-3247
• 页数: 4页
• 分类号: TP301.6
• 字数: 2985字
• 语种: 中文

摘要

在图的最小生成树算法中,Prim和Kruskal算法分别适用于稠密图和稀疏图,但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身.由此,对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图,经实例验证,利用改进的Prim最小生成树算法,根据无向图的顶点数和顶点的度数动态确定求解最小生成树的时间,并将求解的时间复杂度最小化.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	江波	贺州学院计算机科学与工程系	9	91	3.0	9.0