GESP 八级 · GESP 202606 C++ 八级 第 22 题

若一张连通无向图所有边权两两不同，则它的最小生成树一定唯一。

最小生成树：Prim（加点法，O(n²)或O(mlog n)）、Kruskal（加边法，O(mlog m)）。Kruskal需用并查集判环。

Kruskal算法需按边权排序，用并查集判断是否形成环。Prim算法适用于稠密图，Kruskal适用于稀疏图。

【考点】最小生成树（MST）唯一性｜贪心算法确定性｜图连通性

1. 考纲定位：本题直击《GESP大纲》图论算法模块"最小生成树"核心——命题人专门用"边权两两不同"的强条件卡住大量只背结论的考生。MST存在性易证（连通图必存在），但唯一性才是区分点。

2. 解题思维：看到"所有边权不同"立刻联想到Kruskal/Prim贪心过程——每一步选最小边时不可能有平局，所有决策路径唯一，故生成树唯一。通法：任何依赖"局部最优选择无歧义"的贪心算法，若输入中关键参数（如权重）全不同，则最终结果必唯一。

3. 陷阱拆解：B选项利用考生对MST"不唯一"的模糊印象出题；若边权可重复，则相同权重边可互换，MST可能不唯一。题目强调"两两不同"是绝对化表述，若忽略此条件或误以为"连通图MST必不唯一"，必然掉坑。

4. 反命题思维：若将"边权两两不同"改为"边权不全相同"，答案变B；若图不连通，则MST不存在，题目需加"连通"条件。刷到类似题，先问"唯一性的决定性因素是什么"，别被表象迷惑。