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

2023/5/19 0:11:52发布63次查看

1、克鲁斯卡尔算法是求连通网的最小生成树的另一种方法。与普里姆算法不同，它的时间复杂度为o（eloge）（e为网中的边数），所以，适合于求边稀疏的网的最小生成树。
2、克鲁斯卡尔（kruskal）算法从另一途径求网的最小生成树。其基本思想是：假设连通网g=（v，e），令最小生成树的初始状态为只有n个顶点而无边的非连通图t=（v，{}），图中每个顶点自成一个连通分量。在e中选择代价最小的边，若该边依附的顶点分别在t中不同的连通分量上，则将此边加入到t中；否则，舍去此边而选择下一条代价最小的边。依此类推，直至t中所有顶点构成一个连通分量为止。

该用户其它信息

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

VIP推荐

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