🏷️ 知识点：Kruskal算法
下列关于最小生成树的叙述中，正确的是（）。
Ⅰ．最小生成树的代价唯一
Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中
Ⅲ．使用普里姆（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，选边顺序可能不同，结果也可能不同。
易错点
“都是最小生成树”不等于“边集合必相同”；应区分最小代价相同与树形唯一。
用 Kruskal 算法求一个带权连通图的最小生成树。在算法执行的某时刻，已选取的边集合为 TE={(1,2),(2,3),(3,5)}。要选取下一条权值最小的边，不可能选取的边是（ ）。
A. (3,6)
B. (2,4)
C. (1,3)
D. (1,4)
[tag_link]
正确答案：C
结论
选 C。
推导
Kruskal 按边权递增尝试加入边，但若候选边的两个端点已经在同一连通分量中，就会形成回路，必须跳过。TE 已使 1、2、3、5 连成一棵树，因此 (1,3) 会闭合回路，不可能被选入；其余边仍可能连接不同分量。
易错点
“权值最小”不等于“必选”：Kruskal 还要检查加入该边是否成环。