题目

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

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

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

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

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

错因

B

把 II 当对，否定 I。但 I 是对的（MST 代价唯一），II 是错的——只有"权值最小的边唯一"时它才必然在所有 MST 中；如果有多条相同最小权值的边，可以挑其中一些，未必都在某个 MST 里。

举例：3 个顶点构成三角形，三条边权都是 1。每个 MST 选其中 2 条即可，第 3 条最小权边不在该 MST 中。

C

把 III 当对。但 Prim 从不同顶点开始，遇到多条相同权值的边时可能产生不同的 MST。

举例：4 个顶点 1-2-3-4 构成正方形，每条边权都是 1。从顶点 1 开始 Prim 可能选 1-2、2-3、3-4 三条边；从顶点 3 开始可能选 3-2、3-4、4-1 三条边——结构不同。它们的代价都是 3（一样），但 MST 本身不同。

D

把 II 当对（错，原因同 B），又把 IV 当对。IV 错在"绝对化"——边权全唯一时，Prim 和 Kruskal 得到的 MST 完全相同。两者只是构造路径不同（一个从顶点扩散，一个从边贪心），最终结果在边权唯一的情况下必然一致。

总解析

逐项判断：

I 对——MST 的代价（总权值）唯一： 即使 MST 本身不唯一，所有 MST 的边权之和必然相等。这是图论里 MST 的核心性质——证明：假设存在两棵 MST 总权不同，把权小的那棵的某条边换进权大的那棵，能得到更小的生成树，矛盾。

II 错——"所有权值最小的边一定出现在所有 MST 中"是错的： 准确表述应该是"唯一的最小权值边一定在 MST 中"。如果最小权值的边只有一条，去掉它会让代价变大，必含；但如果最小权值边有多条且形成环，可以挑选环之外的边，未必每条都在 MST 里。

III 错——Prim 从不同顶点开始可能产生不同 MST： 当存在等权边时，Prim 在选"下一条最小权边"时如果出现并列，不同起点会做出不同选择。例：正方形 4 顶点全为 1 的边权，从不同角开始 Prim 得到不同的"L 形" MST。

IV 错——Prim 和 Kruskal 不一定不同，等权全唯一时反而一定相同：

• 若所有边权互不相同，MST 唯一，Prim = Kruskal 必然结果相同
• 若有等权边，两者可能给出不同的 MST 或相同的 MST，没有"总不相同"的强约束

只有 I 正确。最终答案是 A。