文献类型：期刊文章

作　　者：江波[1] 张黎[2]

机构地区：[1]贺州学院计算机科学与工程系,广西贺州542800 [2]贺州学院图书馆,广西贺州542800

出　　处：《计算机工程与设计》

基　　金：重庆市信息产业发展政策研究重点基金项目(K2007-53)

年　　份：2009

卷　　号：30

期　　号：13

起止页码：3244-3247

语　　种：中文

收录情况：AJ、BDHX、BDHX2008、CSA、CSA-PROQEUST、CSCD、CSCD_E2011_2012、IC、INSPEC、JST、RCCSE、ZGKJHX、核心刊

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

关 键 词：PRIM算法 最小生成树 无向图 邻接矩阵 邻接多重表  

分 类 号：TP301.6]