下列关于最小生成树的叙述中 正确的是（)。【2020年全国试题8（2分)】 I．最小生成树的代价唯一
最小,试题,代价
已帮助 人
下列关于最小生成树的叙述中，正确的是()。【2020年全国试题8(2分)】 I．最小生成树的代价唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用普里姆(Prim)算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用普里姆算法和克鲁斯卡尔(Kruskal)算法得到的最小生成树总不相同
A．仅I
B．仅Ⅱ
C．仅I、Ⅲ
D．仅Ⅱ、Ⅳ
请帮忙给出正确答案和分析，谢谢！
-
正确答案：A
若有较小的相等权值，最小生成树可能不唯一，但是其代价是唯一的。Ⅱ的错误在于“所有权值最小的边一定会出现在……”，这可能形成环。Ⅲ的错误在于“……最小生成树一定相同”，Ⅳ的错误在于两种算法“……最小生成树总不相同”。若无相同权值，生成树一定相同；若有较小相等权值，生成树可能会不同。