首页 > 代码库 > 最小生成树--Kruskal算法
最小生成树--Kruskal算法
最小生成树
定义：n个顶点网络的生成树有n个结点，n-1条分枝。假设网络中有m条边(m≥n-1)，用MST表示许多可能的生成树的集合，每棵树中n-1条分枝上的权之和用WG(T)表示，则使得WG(Tmin)=Min{WG(T)| T MST}的生成树Tmin便是网络的最小生成树。
构造最小生成树的算法：Prime算法 和Kruskal算法
Kruskal算法
定义：为使生成树上边的权值之和最小，显然，其中每一条边的权值应该尽可能的小。Kruskal算法就是：先构造一个只有n个顶点的子图SG，然后从权值最小的边开始，若它的添加不使SG中产生回路，则SG上加上这条边，如此重复，直至加上n-1条边为止。
特点：Kruskal算法其实是一种贪心(Greedy)算法：
w贪心算法是从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。
贪心算法总是作出在当前看来是最好的选择。
代码：
构造非连通图ST＝（V,{ }）；//此时边为空
k＝i＝0;
//k为被选中的边的数目，i是可选边的序号
While ( k<n-1)
{ ++i;
从边集E中选取第i条权值最小的边(u,v);
若(u,v)加入ST后不使ST中产生回路，
则输出边(u,v)，且k++；
}
最小生成树--Kruskal算法
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。