克鲁斯卡尔算法介绍 克鲁斯卡尔算法简介

   发布日期:2022-09-12 15:31:09     手机:https://m.haocat.cn/zonghe/news156342.html    违规举报
核心提示:1、克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树。2、克鲁斯卡尔(Kruskal)算法从另一途径求网的最小生成树。其基本思想是:

克鲁斯卡尔算法介绍 克鲁斯卡尔算法简介

1、克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同,它的时间复杂度为O(eloge)(e为网中的边数),所以,适合于求边稀疏的网的最小生成树。

2、克鲁斯卡尔(Kruskal)算法从另一途径求网的最小生成树。其基本思想是:假设连通网G=(V,E),令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,{}),图中每个顶点自成一个连通分量。在E中选择代价最小的边,若该边依附的顶点分别在T中不同的连通分量上,则将此边加入到T中;否则,舍去此边而选择下一条代价最小的边。依此类推,直至T中所有顶点构成一个连通分量为止 。

 
 
本文地址:http://haocat.cn/zonghe/news156342.html,转载请注明出处。
 
更多>同类综合百科

推荐图文
推荐综合百科
点击排行
网站首页  |  网站流量  |  联系方式  |  使用协议  |  版权隐私  |  网站地图  |  违规举报  |  SiteMaps  |  BaiDuNews