题目

求下面带权图的最小(代价)生成树时，可能是克鲁斯卡(Kruskal)算法第 2 次选中但不是普里姆(Prim)算法(从 V4 开始)第 2 次选中的边是()。

错因

A

(V1, V3) 权值 = 8。Kruskal 第 2 步可能选它（确实是权 8 的三条候选之一），Prim 从 V4 出发第 2 步也可能选它（V4 加入 V1 后，V1 通向 V3 的边权 = 8，是新一轮最小的）。两者都可能选 → 不满足"Kruskal 可能、Prim 不可能"。

B

(V1, V4) 权值 = 5，是全图最小的边。两个算法的第 1 步都会选它：Kruskal 排序后第一条就是 5；Prim 从 V4 起的第一条出边最小也是 5。所以这条边被算的是"第 1 次选中"，根本不在第 2 次的候选里——已被排除。

D

(V3, V4) 权值 = 8。Kruskal 第 2 步可能选它（权 8 候选之一）。Prim 从 V4 起，第 1 步选了 V1，{V1, V4} 的横切边里 V3-V4 = 8 是最小并列之一，第 2 步也可能选它。两者都可能 → 同样不符。

总解析

先列出所有边、按权升序：

边	权
(V1, V4)	5
(V1, V3)	8
(V2, V3)	8
(V3, V4)	8
(V1, V2)	10
(V2, V4)	11

Kruskal 算法（按边权从小到大，跳过成环的）：

• 第 1 步：选最小边 (V1, V4)，权 5。
• 第 2 步：候选是三条权 = 8 的边 — (V1,V3)、(V2,V3)、(V3,V4)。三条都不会成环（当前森林里 V2、V3 还都是孤立的）。任意一条都可能被选中。

Kruskal 第 2 步候选 = {(V1,V3), (V2,V3), (V3,V4)}

Prim 算法（从 V4 起）：

每一步从"已包含点集 S 到剩余点集"的横切边里选最小的。

• 初始 S = {V4}。

• 第 1 步：S→V̄ 的边有 (V1,V4)=5、(V3,V4)=8、(V2,V4)=11。最小 = (V1,V4)=5，选中。 S = {V1, V4}。

• 第 2 步：S→V̄ 的边里，V̄ = {V2, V3}：

  • (V1, V2) = 10
  • (V1, V3) = 8
  • (V3, V4) = 8
  • (V2, V4) = 11

  最小是 8，候选 = (V1,V3) 和 (V3,V4)。任选其一。

Prim 第 2 步候选 = {(V1,V3), (V3,V4)}

比较两个候选集：

边	Kruskal 第 2 可能选	Prim 从 V4 起第 2 可能选
(V1, V3)	✓	✓
(V2, V3)	✓	✗（V2、V3 都不在 S 中，不是横切边）
(V3, V4)	✓	✓

唯一只在 Kruskal 候选里的是 (V2, V3)。

关键差异：Kruskal 看全局排序、只关心是否成环，所以"两个孤立点之间的最短边" (V2, V3) 也能被选；Prim 必须从已知集 S 向外扩，(V2,V3) 两端都不在 S = {V1, V4} 里，根本不在视野中。这是 Kruskal 与 Prim 在 MST 题里最常考的分野。

最终答案是 C（V2, V3）。