与 Prim算法贪心选择不同,Kruskal算法采取 每次选择权值最小的边的方法,这样,在 不构成环且最后能够连接完所有边它们的权重和一定是最小的。
和之前Prim算法的图一样,便于区别二者。
Kruskal既然是选择最小的边,那么就先找一个最小的出来,是1-6(10)
然后继续找出剩下的边中最小一条边,是3-4(12)
继续找一条最小的出来,2-7(14)
在来,为了区别已经选择的点,我把点的颜色也做个标记,有颜色的表示为已经加入生成树的点
喔,忘了把最小的边2-3(16)选了
现在图变成了这样,(依旧难看)…….
还没找完,继续找最小的边..是7-4(18)
你会发现我把这条边用蓝色标记了,是不是我为了好玩??当然不是了,这条边是有问题的。
再复习下, 生成树:一个连通图的生成树,是一个极小连通子图,其中包含图的所有结点,和构成一棵数的(n-1)条边。如果在一棵生成树的两个结点上添加任意一边,必定构成一个环。
最小生成树:图的所有生成树中所有边的权值和最小的那个生成树。
所以,有环的连生成树都不是了,怎么会是最小生成树。。
所以,这条边7-4(18)丢掉丢掉,重新选择。选择5-4(22)
好像图中所有的点都有颜色了,但是还没完全好,因为它们还不是一条绳上的蚂蚱,
继续选,最短的是6-5(25)
继续选 ,唉,不对,选了24发现又有环了,选28也构成环了。。。。在仔细一看,最小生成树已经生成了
这个就是Kruskal算法的流程。那么接下来说说代码。
这个代码没有写全,因为这样用的次数少的可怜了。都用它的升级版了
Original: https://www.cnblogs.com/ygsworld/p/11256505.html
Author: 回忆酿的甜
Title: 最小生成树-Kruskal算法
原创文章受到原创版权保护。转载请注明出处:https://www.johngo689.com/582150/
转载文章受原作者版权保护。转载请注明原作者出处!