试题-在图G的最小生成树G1中,可能会有某条边的权值超过未选边的权值()

题目

在图G的最小生成树G1中,可能会有某条边的权值超过未选边的权值()

A.对

B.错

解答

正确答案是 A

最小生成树其实是最小权重生成树的简称，只保证了所以权值之和最小，不好找每条路径都有最小权重

C 3条回复评论

落地成盒

最小生成树是针对的无向图，求其权值之和的最小路径，所以不一定能找到最小边长的。

发表于 2018-10-13 15:19:54

雪糕乐

没有很好地理解题意，以为是说在单次选择中放着短的不选去选长的= =

发表于 2018-10-13 15:19:46

老干妈拌面

如果所选的所有边的权值都小于未选边的话，有可能所选路径有回路。所以会抛弃一条短的，选一个不构成回路的

发表于 2018-10-13 15:19:38