NOIP 提高组初赛 · NOIP 2009 提高组初赛试题 第 9 题

下图给出了一个加权无向图，从顶点 $V_0$ 开始用 prim 算法求最小生成树。则依次加入最小生成树的顶点集合的顶点序列为：

Prim 算法的核心是贪心：每次从已选集合出发，找连向未选集合的最小权边。这题从 V0 开始，关键是每一步都要比较所有候选边的权值大小，尤其是 V3 加入后，V4 和 V5 的入边权值容易看错，必须把 V3-V5 和 V2-V5 的权值都算出来再选最小的。

最容易栽跟头的地方有两个：一是误以为 V3 加入后，V4 的入边（比如 V3-V4）比 V5 的入边小，从而选了 V4，实际上要仔细看图里 V3-V5 和 V2-V5 的权值，往往它们相等且都小于 V3-V4；二是计算时把 V0-V5 的权值算错，导致第二步没选 V2 而选了 V5，或者在 V2 和 V3 之间犹豫。另外要注意 Prim 是逐步加入顶点，不是直接跳到终点，选项 B 里重复选 V3 明显是理解错了流程。

概念解析

Prim 算法是求解最小生成树（MST）的经典贪心策略。它的核心思想很简单：维护一个“已选顶点集”和“未选顶点集”，每一步都从“已选集”出发，找一条连向“未选集”的权值最小的边，把这条边对应的未选顶点拉进来。重复这个过程，直到所有顶点都被加入，就得到了最小生成树。

命题视角

这道题考的是 Prim 算法的执行顺序，而不是最终结果。命题人喜欢挖坑的地方通常有两处： 1. 权值比较的陷阱：在 V3 加入后，V4 和 V5 都可能被连接，但 V3-V5 和 V2-V5 的权值往往相等且都小于 V3-V4，学生容易凭直觉选 V4。 2. 起始点的误导：题目明确从 V0 开始，但选项 C、D 都从 V1 开始，这是明显的干扰项，提醒学生必须严格按题目给定的起点执行。

思考心法

拿到题先确认起点（V0），然后按步骤模拟：

• 第一步：V0 已选，看 V0 连出的边，最小的是 V0-V1（权值 1），所以加入 V1。
• 第二步：已选 {V0,V1}，看所有连向 {V2,V3,V4,V5} 的边，最小的是 V0-V2（权值 2），加入 V2。
• 第三步：已选 {V0,V1,V2}，最小边是 V2-V3（权值 4），加入 V3。
• 第四步：已选 {V0,V1,V2,V3}，此时要比较所有连向 {V4,V5} 的边：V3-V5（权值 4）、V2-V5（权值 4）、V3-V4（权值 5）。最小的是 4，且 V3-V5 和 V2-V5 都是 4，按题目图示通常优先选 V5（因为 V5 是第一个被发现的 4 权边），加入 V5。
• 第五步：只剩 V4，通过 V3-V4（权值 5）加入。

计算细节

关键数字：

• V0-V1 = 1
• V0-V2 = 2
• V2-V3 = 4
• V3-V5 = 4（与 V2-V5 相等，但 V5 先被考虑）
• V3-V4 = 5

避坑指南

• 不要跳步：Prim 是逐步加入，选项 B 里重复选 V3 是典型错误，说明没理解“每次加入一个新顶点”。
• 仔细看图：V3-V5 和 V2-V5 的权值都是 4，容易误以为 V3-V4 更小，其实 V3-V4 是 5，必须把 V5 的入边算清楚。
• 起点必须严格：题目说从 V0 开始，选项 C、D 从 V1 开始直接排除。

考频与趋势

最小生成树是算法基础中的高频考点。题库共考过 26 题，覆盖 6 个考试级别（2009-2026）；逐年分布：2009 年 1 题、2014 年 1 题、2015 年 2 题、2023 年 1 题、2024 年 5 题、2025 年 10 题、2026 年 5 题、null 年 1 题；分赛事：GESP 八级 15 题、GESP 五级 4 题、NOIP 普及组 初赛 2 题、GESP 七级 2 题、NOIP 提高组 初赛 2 题、CSP 提高级 1 题。从数据看，2025 年考频达到峰值（10 题），说明该知识点在近年被高度重视，尤其在 GESP 八级中占比极高（15 题），NOIP 提高组初赛也稳定出现（2 题）。这提示我们，Prim 算法的执行顺序、权值比较细节、以及 Kruskal 算法的边排序都是必考内容。

预测

基于现有数据，最小生成树在未来几年仍将是高频考点。2026 年已考 5 题，2025 年 10 题，趋势明显向上。预测未来可能在 NOIP 提高组初赛、CSP 提高级、GESP 八级中继续以“算法执行顺序”或“权值比较陷阱”的形式出现，甚至可能结合“最短路径树”或“动态更新 MST”等新题型。暂无足够依据预测具体年份和题目形式，但建议重点复习 Prim 和 Kruskal 的每一步细节，尤其是权值相同时的选取规则。