一个具有 n 个顶点的连通无向图，它的生成树是包含图中全部顶点的一个极小连通子图，其边数为（ ）。
目标
通过 20 道分层选择题，让学生辨析最小生成树的以下核心点：
- 基本概念：生成树（n 顶点、n-1 条边、无回路）与最小生成树（极小连通子图 + 权值之和最小）；
- 两条核心定理：切分定理（跨割最小边必属某棵 MST）与环性质（环上唯一最大边不属于任何 MST）；
- 算法与复杂度：Prim（跨集合选最小边，朴素 O(n²)、堆 O((n+m)log n)）与 Kruskal（排序后选不成环最小边，O(m log m)）；
- 选型与边界：稠密/稀疏选型、MST 不唯一性、与最短路径树的区别、负权边、不连通图。
题目分三层：基础（★，认定义与性质）、进阶（★★，算法步骤、复杂度与真题）、拔高（★★★，辨析与综合）。
前置知识
建议先阅读 7.2 最小生成树，理解切分定理、环性质，以及 Prim / Kruskal 两种贪心算法各自的适用场景。
作答方法
- 阅读题面后点击一个选项，先写下选择依据；
- 点击“提交答案”，再核对对错、正确答案和题解；
- 做错的题点击“重新作答”后再次推导，直到能说明其余选项为什么不成立；
- 完成全部题目后再使用页面末尾的答案总览复核。
选择题
答题进度已答 0/20正确 0
难度★考点最小生成树、基本概念标识
mst-002对于有 n 个顶点的带权连通图，它的最小生成树是指图中（ ）。
难度★★考点最小生成树、唯一性、408真题标识
mst-003下列关于最小生成树的叙述中，正确的是（ ）。 Ⅰ．最小生成树的代价（权值之和）唯一 Ⅱ．所有权值最小的边一定会出现在所有的最小生成树中 Ⅲ．使用 Prim 算法从不同顶点开始得到的最小生成树一定相同 Ⅳ．使用 Prim 算法和 Kruskal 算法得到的最小生成树总不相同
难度★★考点切分定理、最小生成树、性质标识
mst-004把顶点集分成两个非空部分 S 与 V−S，所有一端在 S、另一端在 V−S 的边称为跨割边。若边 e 是某个割的“最小权跨割边”，则（ ）。
难度★★考点环性质、最小生成树、性质标识
mst-005在连通无向带权图中，若边 e 是某个环上权值最大的边，且在该环上权值最大者唯一，则（ ）。
难度★考点Prim、算法思想标识
mst-006Prim 算法从某个顶点出发构造最小生成树，每一步所做的贪心选择是（ ）。
难度★考点Kruskal、算法思想标识
mst-007Kruskal 算法构造最小生成树时，每一步所做的贪心选择是（ ）。
难度★考点Prim、Kruskal、贪心标识
mst-008Prim 与 Kruskal 算法的共同点是（ ）。
难度★★考点Prim、复杂度标识
mst-009用 Prim 算法求 n 个顶点带权连通图的最小生成树，采用邻接矩阵、朴素实现（每轮线性扫描选最小边）时，时间复杂度是（ ）。
难度★★考点Kruskal、复杂度标识
mst-010用 Kruskal 算法求 m 条边、n 个顶点图的最小生成树，其时间复杂度的主导项是（ ）。
难度★★考点Prim、Kruskal、选型标识
mst-011关于求最小生成树的选型，下列说法正确的是（ ）。
难度★★考点最小生成树、唯一性标识
mst-012最小生成树“不一定唯一”的根本原因是（ ）。
难度★★考点Prim、唯一性标识
mst-013用 Prim 算法从不同顶点开始求同一连通图的最小生成树，结果（ ）。
难度★★★考点最小生成树、最短路径、辨析标识
mst-014关于“最小生成树”与“以某点为源的最短路径树”，下列说法正确的是（ ）。
难度★★★考点最小生成树、负权、边界标识
mst-015关于含负权边的无向图求最小生成树，下列说法正确的是（ ）。
难度★★★考点最小生成树、步骤模拟、综合标识
mst-016无向带权图 G 的顶点为 {A,B,C,D}，边及其权值为 (A,B)=2、(A,C)=3、(A,D)=1、(B,C)=4、(C,D)=5。则 G 的最小生成树权值之和为（ ）。
难度★★考点Prim、步骤模拟标识
mst-017无向带权图 G 的顶点为 {A,B,C,D}，边为 (A,B)=2、(A,C)=3、(A,D)=1、(B,C)=4、(C,D)=5。Prim 从顶点 A 开始，第一步选入的边是（ ）。
难度★考点生成树、基本概念标识
mst-018关于“生成树”与“连通子图”，下列说法正确的是（ ）。
难度★★★考点最小生成树、连通性、边界标识
mst-019对于“不连通”的无向图，下列说法正确的是（ ）。
难度★★考点最小生成树、性质、综合标识
mst-020关于最小生成树，下列叙述中错误的是（ ）。
答案总览（建议完成全部题目后查看）
- 第 1 题：B
- 第 2 题：D
- 第 3 题：A
- 第 4 题：B
- 第 5 题：B
- 第 6 题：B
- 第 7 题：A
- 第 8 题：A
- 第 9 题：B
- 第 10 题：A
- 第 11 题：A
- 第 12 题：A
- 第 13 题：B
- 第 14 题：B
- 第 15 题：B
- 第 16 题：A
- 第 17 题：C
- 第 18 题：B
- 第 19 题：B
- 第 20 题：B
完成清单
思考题
下列题目没有唯一标准答案，目的是把最小生成树从“会做题”推进到“能证明”。建议先独立写一段思路，再对照正文的定理证明。
1. 切分定理与环性质为什么是“对偶”的
切分定理说“跨割的最小边属于某棵 MST”，环性质说“环上唯一最大的边不属于任何 MST”。请试着说明：这两条定理在“最小化”与“最大化”之间、在“选入”与“排除”之间，为什么是对偶的？它们分别对应 Kruskal 的哪一步？
参考思路
切分定理为“选入一条边”提供依据：若某边是跨越当前森林与外部之间的最小边，选它不会错过最优解；环性质为“排除一条边”提供依据，但需区分两种强度：唯一最大边（环上权值唯一最大）不属于任何 MST；并列最大边（如三角形边权 1、2、2）只能保证“存在某棵 MST 不选它”，不能断言它不属于任何 MST。
两者互为“最小化视角”与“最大化视角”的对偶：前者用“局部最小跨割”保证不劣，后者用“局部最大环边”保证可安全省略。Kruskal 的“按权升序、不成环则加入”正是这两条定理的联合体现——每次要么按切分定理选入一条最小边，要么跳过一条会成环的边。注意：Kruskal 跳过成环边依赖的是“存在某棵 MST 不选它”这一安全省略结论，而非“该边不属于任何 MST”；被跳过的边若是并列最大，仍可能属于另一棵 MST。
2. 为什么 MST 的总权值唯一，而树本身可能不唯一
请构造一个最小生成树不唯一的极小例子，并说明：什么时候 MST 是唯一的？切分定理与环性质如何共同决定唯一性？
参考思路
最小例子：三个顶点构成三角形，三条边权都为 1。MST 只需两条边，任取其中两条都构成一棵最小生成树，故共有 3 棵等权 MST，总权都是 2。相比之下，若三条边权为 1、1、2，则只有“两条权为 1 的边”这一种选法，MST 反而唯一。
边权互异只是 MST 唯一的充分条件而非必要条件：只要存在等权边，就要进一步判断这些等权边是否在同一环上可互换。若任意环上都不存在可互换的等权边，MST 仍唯一；反之才不唯一。切分定理与环性质在“边权互异”时对所有边的归属给出唯一裁决，因此边权互异必唯一。
3. Prim 与 Kruskal 为什么都对负权边免疫
最短路径的 Dijkstra 要求边权非负，而最小生成树的 Prim/Kruskal 却对负权完全兼容。请从正确性来源解释：为什么“贪心选最小边”在 MST 里不惧负权，在最短路径里却会因负权失效？
参考思路
MST 的正确性来自切分定理，它只比较“跨割边之间”的相对大小，与边权正负无关；负边只是更小，贪心选最小跨割边依然安全。而 Dijkstra 的正确性依赖“边权非负”来保证“当前 dist 最小的顶点已确定”——负边可能让一条“先经过更大 dist 顶点”的路径更短，从而颠覆“先出队即确定”的贪心序。
一句话：MST 的贪心对象是“局部最小边”（跨割），对符号不敏感；最短路径的贪心对象是“当前最近顶点”，其合法性需要非负权。
复盘
- 我最容易在哪个前提上出错：MST 唯一性、复杂度，还是与最短路径树的区别？
- 哪道题的干扰项最容易混淆？它利用了哪个常见误区？
查看参考答案
复盘时应明确区分：MST 最小化连通全图的总边权，最短路径树最小化指定源点到各点的距离；前者允许负边且不依赖源点，后者的 Dijkstra 需要非负边。还要检查“边权互异必唯一”只是充分条件，以及 Kruskal 的排序复杂度是 O(m log m)。