当前位置:鱼C工作室 >数据结构和算法 > 查看文章

最小生成树(克鲁斯卡尔算法)- 数据结构和算法63

最小生成树(克鲁斯卡尔算法)

 

让编程改变世界

Change the world by program


 

克鲁斯卡尔算法

 

无论是普里姆算法(Prim)还是克鲁斯卡尔算法(Kruskal),他们考虑问题的出发点都是:为使生成树上边的权值之和达到最小,则应使生成树中每一条边的权值尽可能的小。

 

普里姆算法是以某顶点为起点,逐步找各个顶点上最小权值的边来构建最小生成树的。

现在我们换一种思考方式,我们从边出发,因为权值是在边上嘛,直接去找最小权值的边来构建生成树是自然的想法,这也是克鲁斯卡尔算法的精髓。

 

克鲁斯卡尔

克鲁斯卡尔

Kruskal

Kruskal

 

代码演示:参考代码

 

克鲁斯卡尔算法讲解

克鲁斯卡尔算法讲解


为您推荐

报歉!评论已关闭.