Kruskal算法的研究与改进

摘要：

在用Kmskal算法求解最小生成树时,选择边的次数至少为,n-1次;当边数m和顶点数,n满足关系m≤2n-2时,可以对Kruskal算法进行改进.本文用改进的算法求解,选择边的次数最多为,n-1次.改进算法的思想为删除图中权值最大,且删除后不影响图的连通性的边,直到只剩下,n-1条边.改进了的算法在理论上减少了求解时间.

关键词：Kruskal算法、时间复杂度、最小生成树、算法改进

所属期刊栏目：29

分类号：O157.6(代数、数论、组合理论)

资助基金：重庆文理学院学生科研项目XZ2009007

在线出版日期：2010-09-02（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：25-27,32