kruskal算法

解决的问题:

最小生成树

问题描述:

图例描述:
1.首先第一步,我们有一张图Graph,有若干点和边
kruskal算法
2.将所有的边的长度排序,用排序的结果作为我们选择边的依据。这里再次体现了贪心算法的思想。资源排序,对局部最优的资源进行选择,排序完成后,我们率先选择了边AD。这样我们的图就变成了右图
kruskal算法
3.在剩下的变中寻找。我们找到了CE。这里边的权重也是5
kruskal算法
4.依次类推我们找到了6,7,7,即DF,AB,BE。
kruskal算法
5.下面继续选择, BC或者EF尽管现在长度为8的边是最小的未选择的边。但是现在他们已经连通了(对于BC可以通过CE,EB来连接,类似的EF可以通过EB,BA,AD,DF来接连)。所以不需要选择他们。类似的BD也已经连通了(这里上图的连通线用红色表示了)。
最后就剩下EG和FG了。当然我们选择了EG。最后成功的图就是右:
kruskal算法