克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

2019-04-2819:43:09数据结构与算法Comments4,155 views字数 735阅读模式

克鲁斯克尔算法(Kruskal's algorithm)跟普里姆算法一样,是一种用来查找最小生成树的算法,但算法的实现不一样,它是通过对权值从小到大顺序排列来查找最小生成树的。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔算法步骤

1.将原图中所有的边按权值从小到大排序。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

2.从权值最小的边开始,如果这条边连接的两个节点于图中不在同一个已连接的边中,则记录该顶点为已选择。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

3.重复步骤2,直至图中所有的节点都连通,就找到了连通图的最小生成树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔算法时间复杂度

假如我们有 V 表示图中的顶点数,E 表示图中的边数。平均时间复杂度为 克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔算法示例

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

用克鲁斯克尔算法找到加权连通图的最小生成树。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

通过对图中所有边的权值进行排序,得到 AD 边的权值最小为 5,并高亮标记。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

然后下一条权值最小的边是 FH,权值为 6,并高亮标记。(注意不要构成环)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

然后下一条权值最小的边有两条 AB 和 EH,权值为 7,我们任意选一条边 AB,并高亮标记。(注意不要构成环)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

然后下一条权值最小的边是 EH,权值为 7,并高亮标记。(注意不要构成环)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

然后下一条权值最小的边是 HG,权值为 8,并高亮标记。(注意不要构成环)文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

克鲁斯克尔(Kruskal)算法:通过对权值从小到大顺序排列来查找最小生成树

最后一条权值最小的边是 DE,权值为 9,并高亮标记。现在图中所有顶点都连接了,红色连接的边就是最小生成树,最小生成树的权值之和为 42。注意:在权值相同的边,我们可以任意选择一条边,但选择的边不能跟以前的边构成环。如果当权值最小的边跟已选择的边构成了环,就跳过当前的边,继续下一条权值最小的边。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

总结

克鲁斯克尔算法跟普里姆算法一样,是一种用来查找最小生成树的算法。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

对比两个算法,克鲁斯卡尔算法主要是针对边来展开,边数少时效率会非常高,所以对于稀疏图有很大的优势;而普里姆算法对于稠密图,即边数非常多的情况会更好一些。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

作者:清尘闲聊
来源:掘金文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/11632.html

  • 本站内容整理自互联网,仅提供信息存储空间服务,以方便学习之用。如对文章、图片、字体等版权有疑问,请在下方留言,管理员看到后,将第一时间进行处理。
  • 转载请务必保留本文链接:https://www.cainiaoxueyuan.com/suanfa/11632.html

Comment

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定