Question

5． 对如下图所示的无向带权图,按照Kruskal算法求出最小生成树,并画出每一步所得到的中间结果.

Answer 1

第一步我们要做的事情就是将所有的边的长度排序,用排序的结果作为我们选择边的依据.这里 再次体现了贪心算法的思想.资源排序,对局部最优的资源进行选择.

1.选2->4,最小,权值为1；

2,4->5 权值为2 ；

3,4->3;

4:2->1;

5:5->7;

6:4->6;

就得到了最小生成树.