题28

题28

题目

【2012 统考真题】下列关于最小生成树的叙述中, 正确的是 ( ).
I. 最小生成树的代价唯一
II. 所有权值最小的边一定会出现在所有的最小生成树中
III. 使用 Prim 算法从不同顶点开始得到的最小生成树一定相同
IV. 使用 Prim 算法和 Kruskal 算法得到的最小生成树总不相同
A. 仅 I
B. 仅 II
C. 仅 I、III
D. 仅 II、IV

分析

1应该是对的吧，毕竟最小生成树，都是最小了，应该是唯一的
最小生成树是基于贪心的，每一步都是选择可以和当前树连通的，权重最小的，如果这个边无法和当前树连通，哪怕它权重小，应该也不会进入最小生成树
prim算法求最小生成树-aw是基于贪心的，既然每一个，那么选择的起点不同，应该会构造出不同的树
kruskal算法求最小生成树-aw是基于并查集实现的，感觉还是可以和prim算法得到的生成树相同的

解

A
最小生成树的树形可能不唯一 (因为可能存在权值相同的边), 但代价一定是唯一的, 选项 I 正确。
若权值最小的边有多条并且构成环状, 则总有权值最小的边将不出现在某棵最小生成树中,选项 II 错误。
设 个结点构成环, 条边权值相等,另一条边权值较小,则从不同的顶点开始 Prim 算法会得到 种不同的最小生成树,选项 III 错误。
当最小生成树唯一时（各边的权值不同), Prim 算法和 Kruskal 算法得到的最小生成树相同, 选项 IV 错误。