| 基于Prim算法的最小生成树优化研究 |
| |
| 引用本文： | 江波,张黎.基于Prim算法的最小生成树优化研究[J].计算机工程与设计,2009,30(13). |
| |
| 作者姓名： | 江波 张黎 |
| |
| 作者单位： | 1. 贺州学院,计算机科学与工程系,广西,贺州,542800
2. 贺州学院,图书馆,广西,贺州,542800 |
| |
| 基金项目： | 重庆市信息产业发展政策研究重点基金项目 |
| |
| 摘 要： | 在图的最小生成树算法中,Prim和Kruskal算法分别适用于稠密图和稀疏图,但两种算法都不能根据图的顶点数、顶点的度数以及边的分布情况自适应地改变自身.由此,对Prim算法进行改进,从图中每个顶点的度数入手,采取删除某些无用边的思想方法,给出了一个寻找最小生成树的算法,使其能动态调整自身的性能,既适合于稠密图,又适合于稀疏图,经实例验证,利用改进的Prim最小生成树算法,根据无向图的顶点数和顶点的度数动态确定求解最小生成树的时间,并将求解的时间复杂度最小化.
|
| 关 键 词： | Prim算法 最小生成树 无向图 邻接矩阵 邻接多重表 |
Research on minimum spanning tree based on prim algorithm |
| |
| JIANG Bo,ZHANG Li.Research on minimum spanning tree based on prim algorithm[J].Computer Engineering and Design,2009,30(13). |
| |
| Authors: | JIANG Bo ZHANG Li |
| |
| Abstract: | |
| |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ |
|
