Kruskal算法的研究与改进

摘要

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