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

题目

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

A.对

B.错

解答

正确答案是 A

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

C 4条回复评论

窦先生

普里姆算法

图的存贮结构采用邻接矩阵.此方法是按各个顶点连通的步骤进行,需要用一个顶点集合,开始为空集,以后将以连通的顶点陆续加入到集合中,全部顶点加入集合后就得到所需的最小生成树 .所以可能会有某条边的权值超过未选边的权值

发表于 2018-10-24 11:13:13

米米大户

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

发表于 2018-10-24 11:12:53

小小精灵

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

发表于 2018-10-24 11:12:34

小小小可乐

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

发表于 2018-10-24 11:12:23