下列关于最小生成树的叙述中，正确的是（）。

Ⅰ．最小生成树的代价唯一

Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中

Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同

Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同

最小生成树

A. 仅Ⅰ

B. 仅Ⅱ

C. 仅Ⅰ、Ⅲ

D. 仅Ⅱ、Ⅳ

[tag_link]

正确答案：A

对于 Ⅰ， 最小生成树 的树形可能不唯一，但所有最小生成树的总代价都等于全局最小值，因此代价唯一，Ⅰ正确。

对于Ⅱ，若若干条并列最小边本身构成一个环，生成树必须从环中至少舍弃一条边，所以并非每条最小权边都会出现在所有 MST 中，Ⅱ错误。

对于Ⅲ，取 3 个顶点组成三角形，3 条边权值都相同。从不同顶点开始或采用不同的并列边选择顺序，Prim 可得到不同的 MST，Ⅲ错误。

对于Ⅳ，当 MST 唯一时，Prim 与 Kruskal 必须得到同一棵树，因此“总不相同”错误。故仅Ⅰ正确，选 A。