GESP 八级 · GESP 202603 C++ 八级 第 24 题

在图论算法中，Kruskal 算法和 Prim 算法都可以用来求解最小生成树，且这两者的贪心策略无论在任何连通无向图上求得的最小生成树总边权和必定相同。（ ）

贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】最小生成树性质｜贪心算法｜图论基础

1. 🎯 考纲定位

GESP 八级图论模块核心考点，命题人用"总边权和"这个绝对化表述卡住死记算法步骤的考生。