🏷️ 知识点：Prim算法
下列关于最小生成树的叙述中，正确的是（）。
Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同
Ⅳ．使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同
A. 仅Ⅰ
B. 仅Ⅱ
C. 仅Ⅰ、Ⅲ
D. 仅Ⅱ、Ⅳ
[tag_link]
正确答案：A
对于 Ⅰ， 最小生成树 的树形可能不唯一，但所有最小生成树的总代价都等于全局最小值，因此代价唯一，Ⅰ正确。
对于Ⅱ，若若干条并列最小边本身构成一个环，生成树必须从环中至少舍弃一条边，所以并非每条最小权边都会出现在所有 MST 中，Ⅱ错误。
对于Ⅲ，取 3 个顶点组成三角形，3 条边权值都相同。从不同顶点开始或采用不同的并列边选择顺序，Prim 可得到不同的 MST，Ⅲ错误。
对于Ⅳ，当 MST 唯一时，Prim 与 Kruskal 必须得到同一棵树，因此“总不相同”错误。故仅Ⅰ正确，选 A。
用 Prim 算法和 Kruskal 算法构造图的最小生成树，所得到的最小生成树（ ）。
A. 相同 B. 不相同 C. 可能相同，可能不同 D. 无法比较
[tag_link]
正确答案：C
结论
选 C。
推导
两种算法都遵循 MST 的贪心性质。若 MST 唯一，二者必得到同一棵树；若存在等权边导致多个 MST，选边顺序可能不同，结果也可能不同。
易错点
“都是最小生成树”不等于“边集合必相同”；应区分最小代价相同与树形唯一。
用 Prim 算法求一个带权连通图的最小生成树，在算法执行的某个时刻，已选取的顶点集合 U={1,2,3}，已选取的边集合 TE={(1,2),(2,3)}，要选取下一条权值最小的边，应当从（ ）组中选取。
A. {(1,4),(3,4),(3,5),(2,5)} B. {(3,4),(3,5),(4,5),(1,4)} C. {(1,2),(2,3),(3,5)} D. {(4,5),(1,3),(3,5)}
[tag_link]
正确答案：A
结论
选 A。
推导
Prim 的候选边必须横跨割 (U, V−U)，即一端在 {1,2,3}、另一端在未加入顶点集合。只有 A 中的边全部满足该条件；然后从 A 的候选边中选权值最小者。
易错点
已选边 TE 不能再次作为候选；连接 U 内两个顶点的边会形成内部边，不属于 Prim 当前割边集合。