题目

已知无向图 如下图所示，使用克鲁斯卡尔（Kruskal）算法求图 的最小生成树，加入到最小生成树中的边依次是( )。

错因

B

第 3 步本应选权值 9 的 (a, e)，却选了权值 11 的 (b, e)——直接违反了 Kruskal "严格按边权升序选边"的核心规则。可能是看到 (b, e) 与已加入的边相邻就顺手选了，把 Kruskal 当成 Prim 在做。

C

输出顺序看起来像 Prim 算法（从某一顶点出发逐步扩展邻接边）的过程，而不是 Kruskal。Kruskal 不关心边是否与已选边相邻、不依赖起始顶点，只看权值大小。最终的 MST 边集和权值都对，但加入顺序错。

D

同样是 Prim 思维（从 出发的扩展顺序）。第一条边 (a, e) 权 9 不是图中权值最小的边——Kruskal 第一步必须选全图权值最小的边（即 (b, f) 权 5），而不是从某一顶点出发的最小邻接边。

总解析

Kruskal 算法步骤：

1. 把所有边按权值升序排列；
2. 依次扫描每条边：若该边的两个端点不在同一连通分量（用并查集判定），则加入 MST，合并两端点所在分量；否则跳过；
3. 加满 条边即停（ 是顶点数）。

第一步：所有边按权升序排序

序	边	权
1	(b, f)	5
2	(b, d)	6
3	(d, f)	7
4	(a, e)	9
5	(e, c)	10
6	(b, e)	11
7	(a, c)	12
8	(e, d)	14
9	(c, d)	18
10	(a, b)	20

本图 6 个顶点，需选 条边。

第二步：逐边扫描

步	候选边	权	是否成环	决策	当前连通分量
1	(b, f)	5	否	选
2	(b, d)	6	否	选
3	(d, f)	7	是（ 都在 ）	跳过	同上
4	(a, e)	9	否	选
5	(e, c)	10	否	选
6	(b, e)	11	否	选（合并两大分量）	✓

5 条边收齐，算法终止。

第三步：MST 最终形态

加入顺序：，总权值 。

最终答案是 A。

Kruskal vs Prim 的关键区别：Kruskal 看"全局最小边"（不要求与已有 MST 相邻），靠并查集防环；Prim 看"邻接最小边"（必须与已有 MST 相邻），靠"已访问"集合防环。本题选项 C、D 都是 Prim 思路的产物。