请回答下列问题: 画出下列带权图G的所有最小生成树。

admin2018-07-17  27

问题 请回答下列问题:
画出下列带权图G的所有最小生成树。

选项

答案图G的最小生成树如下: [*] 根据kruskal算法,先把c—d的边(权值20)加入集合,而接下来选择下一条边时,因为有两条权值为40的边可以选择,那么因为不同的选择就会生成出不同的最小生成树,若选择b—d,然后同样出现c—d与a—C的选择,而不管先选择哪条边,另一条边也会成为下一个选择的对象,所以这里不影响树的结构,最后答案为左边这棵树,而当之前第二次选择边的时候,选择c—b则会是右边的最小生成树。

解析
转载请注明原文地址:https://jikaoti.com/ti/NcfjFFFM
0

相关试题推荐
最新回复(0)