对某个带权连通图构造最小生成树,以下说法中正确的是______。 Ⅰ.该图的所有最小生成树的总代价一定是唯一的 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ.用普里姆(Prim)算法从不同顶点开始构造的所有最小生成树一定相同 Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
?
wubalubadubdub 回复 2484492098: 对于一个带权连通图构造最小生成树,以下是对各个说法的分析: Ⅰ.该图的所有最小生成树的总代价一定是唯一的:这个说法是正确的。最小生成树的定义就是所有生成树中总权值最小的生成树,所以所有最小生成树的总代价一定是相同的。 Ⅱ.其所有权值最小的边一定会出现在所有的最小生成树中:这个说法是错误的。虽然权值最小的边很可能出现在最小生成树中,但并不是一定的。比如在一个环形图中,任何一条边去掉都能形成一棵最小生成树。 Ⅲ.用普里姆(Prim)算法从不同顶点开始构造的所有最小生成树一定相同:这个说法是错误的。普里姆算法从不同的顶点开始,可能会得到不同的最小生成树。虽然这些最小生成树的权值和是相同的,但是树的结构可能会不同。 Ⅳ.使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同:这个说法是错误的。普里姆算法和克鲁斯卡尔算法都是用来求解最小生成树的,它们可能会得到不同的最小生成树,但也完全可能得到相同的最小生成树。 所以,正确的答案是选项A:仅Ⅰ。
A
用户登录可进行刷题及查看答案
登录后提交答案