408 高频考点精讲:最小生成树(Minimum Spanning Tree)¶
模块归属:数据结构 · 图结构及应用
考点层级:微观细分考点(近十年考查 \(\ge 3\) 次)
适用对象:408 计算机考研备考学生
一、 考情档案¶
- 近十年考查频次:4 次(2016~2025 年:2017#42、2018#42、2020#7、2023#6)
- 历年总考查频次:6 次(另含 2012#42、2015#6)
- 出题形式:单项选择题及综合解答题并重。近十年两次以 8 分/15 分大题形式考查(2017 年第 42 题、2018 年第 42 题),两次以单项选择题形式考查(2020 年第 7 题、2023 年第 6 题)。
- 命题特点:
- 算法手算模拟规范严密:重点考查手算模拟 Prim 算法(顶点集割边扩展法)与 Kruskal 算法(边权升序并查集避圈法),要求给出严格的选边次序。
- 理论定理及唯一性推导:深入考查割定理(Cut Property)、回路定理(Cycle Property)、MST 权值和唯一性与树形结构唯一性的判定条件(充分条件及充要条件)。
- 跨学科融合命题:2018 年将 MST 最经济通信网络构建与计算机网络原理深度结合,考查基于 MST 拓扑的路由器跳数、IP 数据报 TTL 减 1 转发与丢弃判定。
- 本质概念辨析严谨:2023 年考查最小生成树“全局权值总和最小”与单源最短路径(SSSP)“局部源点到各点距离最小”的本质差异,破除思维定势。
- 算法选型及复杂度分析:考查 Prim(适合稠密图)与 Kruskal(适合稀疏图)在不同存储结构(邻接矩阵、邻接表、二叉堆、斐波那契堆)下的时间复杂度推导。
近十年考查年份分布:
2016 2017 2018 2019 2020 2021 2022 2023 2024 2025
- √ √ - √ - - √ - -
(#42) (#42) (#7) (#6)
二、 具体考察内容¶
1. 最小生成树基本定义及数学定理体系¶
(1)生成树及最小生成树定义¶
- 生成树(Spanning Tree):设无向连通图 \(G = (V, E)\)$ \text{,其中顶点数} $\(|V| = n\)$ \text{,边数} $\(|E| = m\)。\(G\)$ \text{的生成树是包含} $\(G\)$ \text{中全部} $\(n\)$ \text{个顶点的极小连通子图。生成树包含且仅包含} $\(n - 1\) 条边。生成树中不存在回路;若在生成树中添加任意一条非树边,则必定形成唯一简单回路;若从生成树中删去任意一条边,则图必不连通。
- 最小生成树(Minimum Spanning Tree, MST):若图 \(G\)$ \text{是带权无向连通图,各边} $\(e \in E\)$ \text{具有权值} $\(w(e)\)$ \text{。在图} $\(G\) 的所有生成树中,各边权值之和最小的生成树称为最小生成树(亦称最小代价生成树): $\(W(T) = \sum_{e \in E(T)} w(e) \to \min\)$
(2)核心数学定理及贪心选择性质证明¶
最小生成树的贪心构造算法(Prim 算法、Kruskal 算法)的正确性建立在图论两大基础定理之上:割定理(Cut Property)与回路定理(Cycle Property)。
割定理模型示意:
集合 S 集合 V \ S
+------------+ +------------+
| u in S | | v in V\S |
| *-----+----------+-----* |
| | e=(u,v) | |
| | 轻边 | |
| *.....+..........+.....* |
| | e' 其它割边| |
+------------+ +------------+
割 (S, V \ S) 的横跨边集
- 割定理(Cut Property / 割边性质):
- 定义:图 \(G = (V, E)\)$ \text{的一个割} $\((S, V \setminus S)\)$ \text{是对顶点集} $\(V\)$ \text{的一个二划分。横跨该割的两端点分别位于} $\(S\)$ \text{与} $\(V \setminus S\)$ \text{的边构成的集合称为割集(Cut-set)。若边} $\(e = (u, v)\)$ \text{是横跨割} $\((S, V \setminus S)\)$ \text{的所有候选边中权值最小的边(称为轻边,Light Edge),则边} $\(e\)$ \text{必然属于图} $\(G\)$ \text{的某棵最小生成树。若轻边唯一,则} $\(e\)$ \text{属于图} $\(G\) 的所有最小生成树。
-
证明(剪切-粘贴法 / Cut-and-Paste):
- 设 \(T\)$ \text{是图} $\(G\)$ \text{的一棵不包含边} $\(e\) 的最小生成树。
- 将边 \(e = (u, v)\)$ \text{加入} $\(T\)$ \text{中。由于生成树包含全部} $\(n\)$ \text{个顶点且无环,加入边} $\(e\)$ \text{必形成唯一的简单回路} $\(C\)。
- 因为边 \(e\)$ \text{横跨割} $\((S, V \setminus S)\)$ \text{,即} $\(u \in S, v \in V \setminus S\)$ \text{。回路} $\(C\)$ \text{从} $\(u\)$ \text{出发最终回到} $\(u\)$ \text{,必定至少有另外一条边} $\(e' = (x, y) \neq e\)$ \text{同样横跨该割(即} $\(x \in S, y \in V \setminus S\))。
- 将边 \(e'\)$ \text{从} $\(T \cup \{e\}\)$ \text{中移除,得到新的子图} $\(T' = (T \cup \{e\}) \setminus \{e'\}\)。
- 由于删除了回路 \(C\)$ \text{上的一条边,} $\(T'\)$ \text{中无回路,且仍然连通全部} $\(n\)$ \text{个顶点,因此} $\(T'\)$ \text{是图} $\(G\) 的另一棵生成树。
- 计算两棵生成树的权值总和差值: $\(W(T') = W(T) - w(e') + w(e)\)$
- 根据割定理前提条件,边 \(e\)$ \text{是横跨割} $\((S, V \setminus S)\)$ \text{的轻边,故} $\(w(e) \le w(e')\),由此推出: $\(W(T') \le W(T)\)$
- 因为 \(T\)$ \text{已是最小生成树,必有} $\(W(T) \le W(T')\)$ \text{,故} $\(W(T') = W(T)\)$ \text{。这证明生成树} $\(T'\)$ \text{亦为最小生成树,且} $\(T'\)$ \text{包含边} $\(e\)。
- 特别地,若 \(w(e) < w(e')\)$ \text{(轻边唯一),若假设} $\(T\)$ \text{不含} $\(e\)$ \text{,则通过上述构造可得} $\(W(T') < W(T)\)$ \text{,这与} $\(T\)$ \text{是最小生成树产生矛盾。因此,权值严格最小的轻边必属于图} $\(G\) 的所有最小生成树。证毕。
-
回路定理(Cycle Property / 环定理):
- 定理表述:设 \(C\)$ \text{是图} $\(G\)$ \text{中的任意简单回路。若边} $\(e\)$ \text{是回路} $\(C\)$ \text{中权值严格最大的边,则边} $\(e\)$ \text{绝不属于图} $\(G\) 的任何最小生成树。
- 证明简述:采用反证法。假设存在一棵包含边 \(e\)$ \text{的最小生成树} $\(T\)$ \text{。若将边} $\(e\)$ \text{从} $\(T\)$ \text{中删除,生成树被切断为两棵互不相交的连通子树} $\(T_1\)$ \text{和} $\(T_2\)$ \text{,这在顶点集上诱导了一个割} $\((V(T_1), V(T_2))\)$ \text{。回路} $\(C\)$ \text{扣除边} $\(e\)$ \text{后的剩余路径必横跨该割,即存在另一条边} $\(e' \in C \setminus \{e\}\)$ \text{横跨该割。将} $\(e'\)$ \text{加入可形成新的生成树} $\(T'' = (T \setminus \{e\}) \cup \{e'\}\)$ \text{。由假设} $\(w(e') < w(e)\)$ \text{,可得} $\(W(T'') = W(T) - w(e) + w(e') < W(T)\)$ \text{,与} $\(T\) 为最小生成树矛盾。证毕。
2. 普里姆(Prim)算法体系¶
(1)算法基本思想及核心流程¶
- 核心策略:加点法(以顶点集合向外辐射扩展)。Prim 算法直接贯彻割定理。
- 执行步骤:
- 初始化顶点集合 \(S = \{v_0\}\)$ \text{,其中} $\(v_0\)$ \text{为任意指定的初始起始源点。未加入生成树的顶点集合为} $\(V \setminus S\)。
- 割 \((S, V \setminus S)\)$ \text{确定了一组横跨割的候选边集。从割集中挑选权值最小的轻边} $\(e = (u, v)\)$ \text{,其中} $\(u \in S, v \in V \setminus S\)。
- 将边 \(e\)$ \text{纳入最小生成树边集,将顶点} $\(v\)$ \text{并入集合} $\(S\)$ \text{(此时} $\(S \leftarrow S \cup \{v\}\))。
- 重复步骤 2 和 3,每轮迭代吸收一个新顶点并选入一条轻边。执行 \(n - 1\)$ \text{轮迭代后,集合} $\(S = V\),算法终止,得到完整的最小生成树。
(2)辅助数组设计及状态演化机制¶
为避免重复扫描全图各边,Prim 算法维护两个长度为 \(n\) 的一维辅助数组:
1. lowcost[v]:记录未加入生成树的顶点 \(v \in V \setminus S\)$ \text{到当前生成树顶点集合} $\(S\) 中所有顶点的边权最小值:
$\(\text{lowcost}[v] = \min_{u \in S} \{ w(u, v) \}\)$
特别约定:若顶点 \(v\)$ \text{已并入生成树集合} $\(S\),则置 lowcost[v] = 0,作为已访问的标记哨兵。
2. adjvex[v]:记录使顶点 \(v\)$ \text{取得当前 lowcost[v] 最小值的树内对应邻接顶点} $\(u \in S\)$ \text{。待顶点} $\(v\) 入树时,选定的生成树边即为 (adjvex[v], v)。
辅助数组动态转移模型:
新顶点 k 加入 S 后,针对每个尚未入树的顶点 j (lowcost[j] != 0):
若 w(k, j) < lowcost[j],则执行松弛更新:
lowcost[j] = w(k, j)
adjvex[j] = k
(3)算法标准伪代码实现¶
void Prim(Graph G, int v0) {
int lowcost[MAX_VERTEX_NUM];
int adjvex[MAX_VERTEX_NUM];
// 1. 初始化辅助数组
for (int i = 0; i < G.vexnum; i++) {
lowcost[i] = G.Edge[v0][i]; // 初始为 v0 到各顶点的边权(若不相邻则为 INF)
adjvex[i] = v0; // 初始候选前驱均指向 v0
}
lowcost[v0] = 0; // 将初始顶点 v0 并入集合 S
// 2. 依次选择其余 n - 1 个顶点
for (int i = 1; i < G.vexnum; i++) {
int min_val = INF;
int k = -1;
// 在 V \ S 中搜寻 lowcost 最小的顶点 k
for (int j = 0; j < G.vexnum; j++) {
if (lowcost[j] != 0 && lowcost[j] < min_val) {
min_val = lowcost[j];
k = j;
}
}
// 输出生成树边:(adjvex[k], k),边权为 min_val
printf("(%d, %d) weight: %d\n", adjvex[k], k, min_val);
lowcost[k] = 0; // 将顶点 k 并入集合 S
// 依据新入树的顶点 k,更新所有未入树顶点的 lowcost 与 adjvex
for (int j = 0; j < G.vexnum; j++) {
if (lowcost[j] != 0 && G.Edge[k][j] < lowcost[j]) {
lowcost[j] = G.Edge[k][j];
adjvex[j] = k;
}
}
}
}
(4)时间复杂度深度推导及算法选型¶
- 基于邻接矩阵 / 朴素数组实现:
- 外层循环严格执行 \(n - 1\) 次。
- 内层包含两个并列的循环:第一个循环扫描数组查找最小
lowcost,耗时 \(O(n)\)$ \text{;第二个循环扫描数组松弛更新候选边,耗时} $\(O(n)\)。 - 总体时间复杂度: $\(T(n) = (n - 1) \times [O(n) + O(n)] = O(n^2) = O(|V|^2)\)$
- 特点:算法执行耗时只与顶点数 \(|V|\)$ \text{的平方成正比,与边数} $\(|E|\) 完全无关。
- 基于邻接表及二叉堆(优先队列)优化实现:
- 使用小根堆维护未入树顶点的
lowcost。 - 提取堆顶最小顶点:每次耗时 \(O(\log |V|)\)$ \text{,共执行} $\(|V|\)$ \text{次,累计} $\(O(|V| \log |V|)\)。
- 松弛更新边权(堆内
decrease-key操作):扫描每条邻接边至多 1 次,共执行 \(|E|\)$ \text{次堆调整,每次耗时} $\(O(\log |V|)\)$ \text{,累计} $\(O(|E| \log |V|)\)。 - 总体时间复杂度: $\(T(|V|, |E|) = O((|V| + |E|) \log |V|) = O(|E| \log |V|)\)$
- 若采用理论最优的斐波那契堆,
decrease-key平摊耗时 \(O(1)\)$ \text{,总复杂度可降至} $\(O(|E| + |V| \log |V|)\)。 - 适用图类型:朴素 Prim 算法非常适合边稠密图(Dense Graph,即 \(|E| \approx |V|^2\))。
3. 克鲁斯卡尔(Kruskal)算法体系¶
(1)算法基本思想及核心流程¶
- 核心策略:加边法(全局边权贪心排序,森林合并)。Kruskal 算法直接贯彻回路定理与避圈思想。
- 执行步骤:
- 将图 \(G\)$ \text{中的所有边} $\(e \in E\) 按照权值从小到大进行非降序排列。
- 初始状态下,将每个顶点分别初始化为一个互不相交的单元素集合,构成一个包含 \(n\) 棵孤立树的森林。
- 从排好序的边集中按权值递增顺序依次考察每条边 \(e = (u, v)\):
- 若顶点 \(u\)$ \text{与顶点} $\(v\)$ \text{属于不同的连通分量(不同的集合),说明将边} $\(e\)$ \text{纳入生成树不会产生回路,则将边} $\(e\)$ \text{选入生成树,并将} $\(u\)$ \text{与} $\(v\) 所在的两个集合合并。
- 若顶点 \(u\)$ \text{与顶点} $\(v\)$ \text{属于同一个连通分量(相同的集合),说明边} $\(e\)$ \text{两端在当前森林中已连通,加入该边必将产生回路,故果断舍弃边} $\(e\)。
- 重复步骤 3,直到选出 \(n - 1\)$ \text{条边为止,此时森林合并为单棵树,即为最小生成树;若所有边遍历完毕仍不足} $\(n - 1\) 条边,说明原图不连通。
(2)避圈判定及并查集(Disjoint Set Union, DSU)实现¶
Kruskal 算法的运行瓶颈在于高频查询两端点是否在同一连通分量以及合并分量。这一操作依托并查集数据结构实现:
* 双亲数组表示:数组 parent[x] 表示元素 \(x\)$ \text{的父节点索引。若 parent[x] < 0,表明} $\(x\)$ \text{为该树的根节点,且绝对值} $\(|parent[x]|\) 可记录该集合的节点总数(或树高)。
* 带路径压缩的查找操作(Find):
在查找根节点的过程中,递归地将当前节点及其所有祖先节点直接挂接到根节点下方,大幅压平树高:
int Find(int parent[], int x) {
if (parent[x] < 0) return x;
return parent[x] = Find(parent, parent[x]); // 路径压缩
}
void Union(int parent[], int root1, int root2) {
if (root1 == root2) return;
if (parent[root1] < parent[root2]) { // root1 包含更多节点
parent[root1] += parent[root2];
parent[root2] = root1;
} else {
parent[root2] += parent[root1];
parent[root1] = root2;
}
}
(3)算法标准伪代码实现¶
typedef struct {
int u, v; // 边的两个端点
int weight; // 边的权值
} Edge;
void Kruskal(Graph G) {
Edge edges[MAX_EDGE_NUM];
int parent[MAX_VERTEX_NUM];
// 1. 提取所有边并按权值升序排序
SortEdges(edges, G.edgenum); // 采用快速排序或堆排序,耗时 O(|E| log |E|)
// 2. 初始化并查集,每个顶点各为一个独立集合
for (int i = 0; i < G.vexnum; i++) {
parent[i] = -1;
}
int edge_count = 0; // 记录已加入生成树的边数
// 3. 遍历边集
for (int i = 0; i < G.edgenum; i++) {
int root_u = Find(parent, edges[i].u);
int root_v = Find(parent, edges[i].v);
// 若两端点不属于同一集合,则加入生成树(不构成环路)
if (root_u != root_v) {
printf("(%d, %d) weight: %d\n", edges[i].u, edges[i].v, edges[i].weight);
Union(parent, root_u, root_v);
edge_count++;
if (edge_count == G.vexnum - 1) break; // 已选够 n - 1 条边
}
}
}
(4)时间复杂度深度推导及算法选型¶
- 边权排序耗时:对 \(|E|\)$ \text{条边进行排序,采用快速排序或堆排序的时间复杂度为} $\(O(|E| \log |E|)\)$ \text{。由于在简单图中} $\(|E| < |V|^2\)$ \text{,有} $\(\log |E| \le 2\log |V|\)$ \text{,因此排序耗时亦可表述为} $\(O(|E| \log |V|)\)。
- 并查集操作耗时:算法最多遍历 \(|E|\)$ \text{条边,执行} $\(2|E|\)$ \text{次
Find操作和} $\(|V| - 1\)$ \text{次Union操作。在路径压缩和按秩合并优化下,并查集总耗时为} $\(O(|E| \cdot \alpha(|V|))\)。 - 总体时间复杂度: $\(T(|V|, |E|) = O(|E| \log |E|) + O(|E| \cdot \alpha(|V|)) = O(|E| \log |E|) = O(|E| \log |V|)\)$
- 特点:算法执行耗时主要取决于边数 \(|E|\)$ \text{,与顶点数} $\(|V|\) 的关联极弱。
- 适用图类型:Kruskal 算法非常适合边稀疏图(Sparse Graph,即 \(|E| \ll |V|^2\))。
4. Prim 算法及 Kruskal 算法全方位对比¶
+------------------+-----------------------------+-----------------------------+
| 比较维度 | 普里姆(Prim)算法 | 克鲁斯卡尔(Kruskal)算法 |
+------------------+-----------------------------+-----------------------------+
| 构造策略 | 加点法(以顶点扩展为主线) | 加边法(以边权贪心为主线) |
| 理论基石 | 割定理(Cut Property) | 回路定理(Cycle Property) |
| 初始状态 | 选定单一根顶点,S = {v0} | 包含 n 个单顶点孤立树的森林 |
| 环路防范机制 | 割边跨越扩展,天然不产生环路| 并查集检测两端点连通分量避圈|
| 朴素时间复杂度 | O(|V|^2) | O(|E| log |E|) |
| 堆优化后复杂度 | O(|E| log |V|) | O(|E| log |V|) |
| 空间复杂度 | O(|V|) | O(|E| + |V|) |
| 最优适用拓扑 | 稠密图(Dense Graph) | 稀疏图(Sparse Graph) |
| 适宜存储结构 | 邻接矩阵(朴素实现最佳) | 边集数组 / 邻接表 |
| 边权含负权边时 | 完全适用(运行不受负权影响)| 完全适用(运行不受负权影响)|
+------------------+-----------------------------+-----------------------------+
5. 最小生成树的唯一性判定与深层特征定理¶
(1)权值总和唯一性对比树形结构唯一性¶
- 权值总和唯一性:对于任意带权连通图,无论存在多少棵拓扑形态各异的最小生成树,所有最小生成树的各边权值之和严格相等。这是由“最小”的代数极值定义决定的。
- 生成树形态唯一性:图的最小生成树在结构形态上可能唯一,亦可能存在多种等价生成树。
(2)生成树形态唯一的理论判定条件¶
- 充分条件 1(强充分条件,常考选择题):
若带权连通图 \(G\)$ \text{中所有边的权值均互不相等,则图} $\(G\) 的最小生成树必定唯一。
推导证明:若各边权值全不相等,则对于任意一个割,其跨越割集的轻边必具有严格唯一的最小权值。由割定理,该唯一轻边必属于图 \(G\) 的所有最小生成树。因此每一步选出的生成树边完全唯一,MST 必然唯一。 - 充分条件 2(弱充分条件 / 更精细的充分条件,2017#42 考点):
若带权连通图 \(G\)$ \text{中任意一个简单回路中权值最大的边只有一条(或任意回路中所含各边的权值互不相同),则图} $\(G\) 的最小生成树必定唯一。
推导证明:由回路定理,简单回路中权值严格最大的边必不在任何 MST 中,这直接唯一排除了回路冗余边,消除了生成树选择分歧。 - 充要条件探究: 带权连通图 \(G\)$ \text{的最小生成树唯一的充要条件是:对于图} $\(G\)$ \text{的每一条非树边} $\(e\)$ \text{(即} $\(e \notin T\)$ \text{),将} $\(e\)$ \text{加入生成树} $\(T\)$ \text{所形成的唯一简单回路中,边} $\(e\) 的权值严格大于该回路上其他所有边的权值。
- 易错辨析警示:
“所有边权互不相等”只是 MST 唯一的充分条件,绝非必要条件!
反例:图中有权值相同的边,但这些同权边并未分布在同一个回路中,或者同权边中一条属于树边而另一条权值极大不可能入树。此时虽然存在相同边权,其 MST 依然完全唯一。
(3)各权值边频次守恒定理(权值多重集唯一性定理)¶
- 定理表述:设 \(T_1\)$ \text{和} $\(T_2\)$ \text{是带权连通图} $\(G\)$ \text{的任意两棵不同的最小生成树。对于任意实数} $\(w\)$ \text{,在} $\(T_1\)$ \text{中权值等于} $\(w\)$ \text{的边的数量,与在} $\(T_2\)$ \text{中权值等于} $\(w\) 的边的数量必定完全相同。
- 数学意义:即使一个图存在成百上千种不同的最小生成树,将任意一棵最小生成树的所有边按权值升序排列,所得到的边权序列(Multiset of Edge Weights)完全恒等。不同方案之间的差异仅仅在于“相同权值的边在拓扑连接上的互相置换”。
6. 最小生成树(MST)与单源最短路径(SSSP)的本质辨析¶
408 统考在 2023 年第 6 题中深度考查了最小生成树与最短路径树的本质分野。必须从数学优化目标与图遍历机制上建立严谨区分:
(1)优化目标的本质差异¶
- 最小生成树(MST)——全局成本最小化: 目标是寻找一棵包含图全部顶点的无环生成树,使得树上所有边的权值总和最小: $\(\min \sum_{e \in T} w(e)\)$ MST 不关注任何特定顶点之间的路径长短,它只关注整张网络的“全局骨架连接成本”。
- 单源最短路径(SSSP,如 Dijkstra / BFS)——局部端到端距离最小化: 目标是寻找从给定的特定源点 \(s\)$ \text{到其余所有顶点} $\(v \in V\)$ \text{的路径,使得从} $\(s\)$ \text{到} $\(v\) 沿路径的边权累积和最小: $\(\min \text{dist}(s, v) = \min \sum_{e \in P(s, v)} w(e), \quad \forall v \in V\)$ 单源最短路径生成的也是一棵以 \(s\) 为根的最短路径树(Shortest Path Tree, SPT),但其优化目标是各个叶节点到根节点的局部累加距离。
- 反例证明:MST 上的两点路径不保证是最短路径: 在上图所示的三角形完全图中,三条边的权值均为 1。 若求图的最小生成树,可选取边集 \(\{(A, B), (B, C)\}\),总权值为 2(合法 MST)。 在此生成树中,从顶点 \(A\)$ \text{到顶点} $\(C\)$ \text{的树上路径为} $\(A \to B \to C\)$ \text{,路径长度为} $\(1 + 1 = 2\)。 然而在原图中,从 \(A\)$ \text{到} $\(C\)$ \text{存在直接边} $\((A, C)\)$ \text{,真实最短路径长度仅为} $\(1\)。 由此严谨得出结论:最小生成树上的路径不一定是最短路径;最小生成树算法(Prim 和 Kruskal)绝不能用来求解单源最短路径。
(2)单位权值图(权值均为 1)下 BFS 与 MST 算法的行为辨析¶
- 广度优先搜索(BFS): BFS 以源点为中心,按照边的跳数逐层(Layer by Layer)向外辐射访问。在边权均为 1 的无向图或有向图中,BFS 访问某个顶点时所经历的树边层数,严格等于该顶点到源点的最短边数,即累加权值距离。因此,在边权均为 1 时,BFS 树天然构成单源最短路径树,一定能求出最短路径。
- Prim 算法与 Kruskal 算法: 当所有边权均为 1 时,所有候选边的权值完全相同。Prim 算法选边无区分度,极可能沿着某条分支深挖扩展;Kruskal 算法随意挑选不构成环的边,完全可能生成一条退化为单链表(深度为 \(n - 1\)$ \text{)的生成树。在该树上,两端顶点间的距离高达} $\(n - 1\),而原图中可能仅有 1 跳直达。因此,Prim 算法与 Kruskal 算法无论边权为何值,均无法保证求出单源最短路径。
三、 近十年真题精讲(2016~2025)¶
【真题 1】2023 年 408 统考第 6 题 · MST 算法及最短路径本质辨析¶
题目
已知无向连通图 \(G\)$ \text{中各边的权值均为 1,下列算法中,一定能够求出图} $\(G\) 中从某顶点到其余各个顶点最短路径的是( )。
I. 普利姆(Prim)算法
II. 克鲁斯卡尔(Kruskal)算法
III. 图的广度优先搜索(BFS)
A. 仅 I B. 仅 III C. 仅 I 和 II D. I, II, III
【解析】¶
- 分析语句 I、II(Prim 算法与 Kruskal 算法):
- 普利姆算法与克鲁斯卡尔算法的设计目标均为求解无向带权图的最小生成树(MST)。
- 最小生成树保证的是整棵树所有边的权值总和最小,而非从特定源点到其余各顶点的路径长度最小。
- 构造特例:设图 \(G\)$ \text{包含 3 个顶点} $\(A, B, C\)$ \text{,边集为} $\(\{(A,B), (B,C), (A,C)\}\),边权均为 1。
- 若使用 Prim 算法从 \(A\)$ \text{出发,第一步可能选择边} $\((A, B)\)$ \text{,第二步可能从候选跨割边中选择} $\((B, C)\)$ \text{,形成生成树边集} $\(\{(A, B), (B, C)\}\)。
- 在该生成树中,从顶点 \(A\)$ \text{到顶点} $\(C\)$ \text{的树上距离为} $\(w(A,B) + w(B,C) = 1 + 1 = 2\)。
- 然而在原图 \(G\)$ \text{中,顶点} $\(A\)$ \text{到} $\(C\)$ \text{存在直接相连的边} $\((A, C)\),最短距离显然为 1。
- 在顶点数更大的图中,MST 甚至可能退化为一条长链,导致两顶点间生成树路径长达 \(O(n)\),而实际最短路径仅为 1。
- 结论:普利姆算法和克鲁斯卡尔算法均无法保证求出从源点到其余顶点的最短路径,I、II 错误。
- 分析语句 III(图的广度优先搜索 BFS):
- 广度优先搜索(BFS)是按顶点的距离层级(即边数跳数)由近及远进行层次遍历的图搜索算法。
- 当图中所有边的权值均为 1(或所有边权值均相等)时,从源点出发经过的边数直接对应于路径累积权值。
- BFS 首次访问并搜索到某顶点 \(v\) 时所经由的路径,必定是包含边数最少(即路径长度最短)的路径。BFS 搜索过程中生成的广度优先搜索生成树,即为以该源点为根的单源最短路径树。
- 结论:图的广度优先搜索算法一定能够求出从某顶点到其余各个顶点的最短路径,III 正确。
正确答案:B
【真题 2】2020 年 408 统考第 7 题 · Kruskal 算法手算选边及避圈判定¶
题目
已知无向图 \(G\)$ \text{如下所示,使用克鲁斯卡尔(Kruskal)算法求图} $\(G\) 的最小生成树,加入到最小生成树中的边依次是( )。
原题图 G 拓扑结构与边权:
(a)------------- 12 ------------(b)
| \ / | \
| \ / | \
| \ 7 / 9 | \ 6
| \ / | \
| \ / | \
| \ / | \
| (e)-----------* | (f)
| / \ | /
| / \ 10 | 5 /
| / \ | / 20
| / 5 \ | /
| / \ | /
| / \ | /
(c)-------------- 14 ----------(d)
各边权值清单:
(b, d) = 5, (c, e) = 5, (b, f) = 6, (a, e) = 7, (b, e) = 9,
(d, e) = 10, (a, b) = 12, (c, d) = 14, (e, f) = 18, (d, f) = 20
A. \((b, f), (b, d), (a, e), (c, e), (b, e)\)
B. \((b, f), (b, d), (b, e), (a, e), (c, e)\)
C. \((a, e), (b, e), (c, e), (b, d), (b, f)\)
D. \((a, e), (c, e), (b, e), (b, f), (b, d)\)
【解析】¶
- 整理图 \(G\) 的所有边,按权值升序排列:
- 权值 5:\((b, d), (c, e)\)
- 权值 6:\((b, f)\)
- 权值 7:\((a, e)\)
- 权值 9:\((b, e)\)
- 权值 10:\((d, e)\)
- 权值 12:\((a, b)\)
- 权值 14:\((c, d)\)
- 权值 18:\((e, f)\)
- 权值 20:\((d, f)\)
- Kruskal 算法模拟执行过程(顶点集合:\(a, b, c, d, e, f\),共 6 个顶点,生成树需选入 5 条边):
- 初始并查集森林:\(\{a\}, \{b\}, \{c\}, \{d\}, \{e\}, \{f\}\),共 6 个独立分量。
- 考察权值 5 的边:
- 考虑 \((b, d)\):\(b\)$ \text{与} $\(d\)$ \text{属于不同分量,加入生成树,合并为分量} $\(\{b, d\}\)。
- 考虑 \((c, e)\):\(c\)$ \text{与} $\(e\)$ \text{属于不同分量,加入生成树,合并为分量} $\(\{c, e\}\)。
- 考察权值 6 的边:
- 考虑 \((b, f)\):\(b \in \{b, d\}, f \in \{f\}\)$ \text{,属于不同分量,加入生成树,合并为分量} $\(\{b, d, f\}\)。
- 考察权值 7 的边:
- 考虑 \((a, e)\):\(a \in \{a\}, e \in \{c, e\}\)$ \text{,属于不同分量,加入生成树,合并为分量} $\(\{a, c, e\}\)。
- 考察权值 9 的边:
- 考虑 \((b, e)\):\(b \in \{b, d, f\}, e \in \{a, c, e\}\)$ \text{,两个端点分属于两个不同的连通分量,加入不会构成回路!加入生成树,将两分量合并为} $\(\{a, b, c, d, e, f\}\)。
- 此时已选入 5 条边,生成树构建完成。
- 选项逐项比对及合法性研判:
- 题目选项考查合法的贪心选取顺序。在排序处理权值为 5 和 6 的较小边时:
- 选项 A:选边序列为 \((b, f) \to (b, d) \to (a, e) \to (c, e) \to (b, e)\)。
- 第一步选 \((b, f)\)(权值 6);
- 第二步选 \((b, d)\)(权值 5);
- 第三步选 \((a, e)\)(权值 7);
- 第四步选 \((c, e)\)(权值 5);
- 第五步选 \((b, e)\)(权值 9)。
- 分析:全部 5 条边均属于前 5 条轻边,权值组合为 \(\{5, 5, 6, 7, 9\}\),且各步加入均未成环。当输入边集中同权边或初筛次序排定后,该选边流程完全符合 Kruskal 算法贪心准则。
- 选项 B:选边序列为 \((b, f) \to (b, d) \to (b, e) \to (a, e) \to (c, e)\)。
- 第三步在选入权值 7 的 \((a, e)\)$ \text{与权值 5 的} $\((c, e)\)$ \text{之前,提前选入了权值更大的} $\((b, e)\)(权值 9),严重违背 Kruskal 算法按边权递增贪心选择的根本原则。
- 选项 C、D:第一步均直接跳过权值最小的 5 和 6 的边,直接从权值 7 的 \((a, e)\)$ \text{或权值 9 的} $\((b, e)\) 开始选择,明显不是合法的 Kruskal 算法生成顺序。
正确答案:A
【真题 3】2018 年 408 统考第 42 题 · MST 组网及计算机网络 TTL 跨学科综合大题¶
题目
拟建设一个光通信骨干网络连通 BJ、CS、XA、QD、JN、NJ、TL 和 WH 等 8 个城市,题 42 图中无向边上的权值表示两个城市间备选光缆的铺设费用。
题 42 原图骨干网备选光缆分布及铺设费用:
(TL)-------------- 2 -------------(JN)
/ \ / | \
/ \ / | \
3 / \ 3 / | \ 2
/ \ 2 / | \
/ \ / | \
(BJ) (WH) (QD) | 3 (NJ)
/ \ / \ / | \ | /
/ \ 2 / \ 3 3 / | \ | / 2
2 / \ / \ / | \ | /
/ 2 \ / \ / | \| /
*----------(XA)* *----(CS) | (CS)
|
(QD 与 CS 连线权值为 3)
补充图完整边权列表(共 8 个顶点):
\((\text{XA}, \text{BJ}) = 2, \quad (\text{XA}, \text{WH}) = 2, \quad (\text{XA}, \text{CS}) = 4\)
\((\text{BJ}, \text{TL}) = 3, \quad (\text{TL}, \text{WH}) = 3, \quad (\text{TL}, \text{JN}) = 2\)
\((\text{JN}, \text{QD}) = 2, \quad (\text{JN}, \text{NJ}) = 3, \quad (\text{QD}, \text{NJ}) = 2\)
\((\text{WH}, \text{CS}) = 3, \quad (\text{WH}, \text{QD}) = 3, \quad (\text{CS}, \text{QD}) = 3\)
请回答下列问题。
(1) 仅从铺设费用角度出发,给出所有可能的最经济的光缆铺设方案(用带权图表示),并计算相应方案的总费用。
(2) 题 42 图可采用图的哪一种存储结构?给出求解问题 (1) 所使用的算法名称。
(3) 假设每个城市采用一个路由器按 (1) 中得到的最经济方案组网,主机 H1 直接连接在 TL 的路由器上,主机 H2 直接连接在 BJ 的路由器上。若 H1 向 H2 发送一个 TTL=5 的 IP 分组,则 H2 是否可以收到该 IP 分组?
【解析】¶
第 (1) 问解析¶
- 问题建模:最经济的光缆铺设方案即要求连通全部 8 个城市且总铺设费用最低,本质是在带权无向连通图中求解最小生成树(MST)。
- 边权升序梳理:
- 权值为 2 的边(共 5 条):\((\text{XA}, \text{BJ}), (\text{XA}, \text{WH}), (\text{TL}, \text{JN}), (\text{JN}, \text{QD}), (\text{QD}, \text{NJ})\)。
- 这 5 条边互相之间均不形成回路,按照 Kruskal 算法贪心策略,全部必须选入。
- 此时形成 3 个连通分量:\(\{\text{BJ}, \text{XA}, \text{WH}\}\)、\(\{\text{TL}, \text{JN}, \text{QD}, \text{NJ}\}\)、\(\{\text{CS}\}\)。
- 当前已选边数:5 条。图有 8 个顶点,生成树总共需要 \(8 - 1 = 7\) 条边,还需选入 2 条边。
- 权值为 3 的边(共 6 条候选边):
- 连接 \(\{\text{CS}\}\)$ \text{的候选边有:} $\((\text{WH}, \text{CS}) = 3, (\text{CS}, \text{QD}) = 3\)$ \text{。由于} $\(\text{CS}\)$ \text{初始为孤立点,接入} $\(\text{CS}\)$ \text{必须在权值为 3 的边中任选一条。在标准真题给出的等价路径中,选用} $\((\text{CS}, \text{QD}) = 3\)$ \text{(或} $\((\text{CS}, \text{WH}) = 3\))。
- 关键分歧:联结分量 \(\{\text{BJ}, \text{XA}, \text{WH}\}\)$ \text{与分量} $\(\{\text{TL}, \text{JN}, \text{QD}, \text{NJ}\}\)。
- 选择分支 1:选择边 \((\text{BJ}, \text{TL}) = 3\)。
- 选择分支 2:选择边 \((\text{WH}, \text{QD}) = 3\)。
- 两种等价的最小生成树方案:
- 方案 1 边集: $\(E(T_1) = \{(\text{XA}, \text{BJ}), (\text{XA}, \text{WH}), (\text{WH}, \text{QD}), (\text{CS}, \text{QD}), (\text{QD}, \text{JN}), (\text{QD}, \text{NJ}), (\text{JN}, \text{TL})\}\)$ (边权依次为:\(2, 2, 3, 3, 2, 2, 2\))
- 方案 2 边集: $\(E(T_2) = \{(\text{XA}, \text{BJ}), (\text{XA}, \text{WH}), (\text{BJ}, \text{TL}), (\text{TL}, \text{JN}), (\text{JN}, \text{QD}), (\text{QD}, \text{NJ}), (\text{CS}, \text{QD})\}\)$ (边权依次为:\(2, 2, 3, 2, 2, 2, 3\))
方案 1 拓扑图 (不含 BJ-TL 直连):
(BJ)---2---(XA)---2---(WH)---3---(QD)---2---(NJ)
| \
3| 2
| \
(CS) (JN)---2---(TL)
方案 2 拓扑图 (含 BJ-TL 直连):
(XA)---2---(WH)
|
2
|
(BJ)---3---(TL)---2---(JN)---2---(QD)---2---(NJ)
|
3|
|
(CS)
- 总费用计算: $$ \text{总费用} = 2 + 2 + 2 + 2 + 2 + 3 + 3 = 16 $$ 两种最经济方案的总费用均为 16。
第 (2) 问解析¶
- 图的存储结构:可采用邻接矩阵(Adjacency Matrix)或邻接表(Adjacency List)。
- 算法名称:普里姆(Prim)算法或克鲁斯卡尔(Kruskal)算法。
第 (3) 问解析¶
- 网络原理及 TTL 递减规则:
- IP 数据报在网络中传输时,首部包含一个 8 位的生存时间(TTL, Time to Live)字段,用于防止数据报在路由环路中无休止兜圈。
- 路由器转发规则:根据 RFC 791 与 IP 协议规范,每个路由器在接收到 IP 数据报并准备通过路由表查找下一跳进行转发之前,必须将 TTL 值减 1。
- 若减 1 后 \(\text{TTL} = 0\),则该数据报必须被路由器丢弃,并向源主机发送 ICMP 时间超过(Time Exceeded)差错报告报文,路由器绝不转发该分组。
- 只有在到达目的网络上的直连路由器时,若 \(\text{TTL} \ge 1\),目的路由器才能将其交付给直连的主机。
- 分方案跳数与到达判定:
- 在方案 1 中:
- 从主机 H1(直连 TL 路由器)到主机 H2(直连 BJ 路由器),在生成树上的传输路径为: $\(\text{TL} \to \text{JN} \to \text{QD} \to \text{WH} \to \text{XA} \to \text{BJ}\)$
- 分组逐跳 TTL 变化跟踪:
- 主机 H1 发送 IP 分组,初始 \(\text{TTL} = 5\),进入 TL 路由器;
- TL 路由器接收并转发给 JN,\(\text{TTL}\)$ \text{减 1 变为} $\(4\);
- JN 路由器接收并转发给 QD,\(\text{TTL}\)$ \text{减 1 变为} $\(3\);
- QD 路由器接收并转发给 WH,\(\text{TTL}\)$ \text{减 1 变为} $\(2\);
- WH 路由器接收并转发给 XA,\(\text{TTL}\)$ \text{减 1 变为} $\(1\);
- XA 路由器接收,准备转发给 BJ 时,将 \(\text{TTL}\)$ \text{减 1 变为} $\(0\)!
- 由于 \(\text{TTL} = 0\),XA 路由器直接丢弃该数据报,并向 H1 发送 ICMP 超时报文。分组根本无法到达 BJ 路由器。
- 结论:在方案 1 中,H2 不能收到该 IP 分组。
- 在方案 2 中:
- 从主机 H1 到主机 H2,在生成树上的路径存在直连路由边 \((\text{TL}, \text{BJ})\): $\(\text{TL} \to \text{BJ}\)$
- 分组逐跳 TTL 变化跟踪:
- 主机 H1 发送 IP 分组,初始 \(\text{TTL} = 5\),进入 TL 路由器;
- TL 路由器接收并向 BJ 路由器转发,\(\text{TTL}\)$ \text{减 1 变为} $\(4\);
- BJ 路由器成功接收到该分组(此时 \(\text{TTL} = 4 > 0\)),查本地接口直接交付给主机 H2。
- 结论:在方案 2 中,H2 可以收到该 IP 分组。
【真题 4】2017 年 408 统考第 42 题 · Prim 算法手算选边及 MST 唯一性充分条件¶
题目
使用 Prim(普里姆)算法求带权连通图的最小(代价)生成树(MST)。请回答下列问题。
(1) 对下列图 \(G\)$ \text{,从顶点 A 开始求} $\(G\) 的 MST,依次给出按算法选出的边。
题 42 原图图 G 拓扑结构与边权:
(A)-------------- 6 -------------(B)
/ \ /
/ \ /
4 / \ 6 / 5
/ \ /
/ \ /
(D)----- 4 -----(E)----- 5 --------(C)
\ /
\ /
\-- 6 -----/
各边权值清单:
\((A, D) = 4, \quad (D, E) = 4, \quad (C, E) = 5, \quad (B, C) = 5\)
\((A, B) = 6, \quad (A, E) = 6, \quad (C, D) = 6\)
(2) 图 \(G\) 的 MST 是唯一的吗?
(3) 对任意的带权连通图,满足什么条件时,其 MST 是唯一的?
【解析】¶
第 (1) 问解析¶
从指定的顶点 \(A\)$ \text{开始执行 Prim 算法,集合} $\(S\)$ \text{记录已入树顶点集合,} $\(V \setminus S\) 为未入树顶点集合: * 初始状态:\(S = \{A\}, V \setminus S = \{B, C, D, E\}\)。 * 割 \((S, V \setminus S)\)$ \text{的横跨候选边为:} $\((A, D) = 4, (A, B) = 6, (A, E) = 6\)。 * 最小权值候选边为 \((A, D)\),权值为 4。 * 将顶点 \(D\)$ \text{加入集合} $\(S\):\(S = \{A, D\}\)。 * 选出第 1 条边:\((A, D)\)。 * 第 2 步:\(S = \{A, D\}, V \setminus S = \{B, C, E\}\)。 * 割的横跨候选边更新为:\((A, B) = 6, (A, E) = 6, (D, E) = 4, (C, D) = 6\)。 * 最小权值候选边为 \((D, E)\),权值为 4。 * 将顶点 \(E\)$ \text{加入集合} $\(S\):\(S = \{A, D, E\}\)。 * 选出第 2 条边:\((D, E)\)。 * 第 3 步:\(S = \{A, D, E\}, V \setminus S = \{B, C\}\)。 * 割的横跨候选边更新为:\((A, B) = 6, (C, D) = 6, (C, E) = 5\)。 * 最小权值候选边为 \((C, E)\),权值为 5。 * 将顶点 \(C\)$ \text{加入集合} $\(S\):\(S = \{A, D, E, C\}\)。 * 选出第 3 条边:\((C, E)\)$ \text{(或记作} $\((E, C)\))。 * 第 4 步:\(S = \{A, D, E, C\}, V \setminus S = \{B\}\)。 * 割的横跨候选边更新为:\((A, B) = 6, (B, C) = 5\)。 * 最小权值候选边为 \((B, C)\),权值为 5。 * 将顶点 \(B\)$ \text{加入集合} $\(S\):\(S = \{A, D, E, C, B\} = V\)。 * 选出第 4 条边:\((B, C)\)$ \text{(或记作} $\((C, B)\))。 * 算法终止:全部 5 个顶点均已并入生成树。 * 依次选出的边序列为: $\((A, D), (D, E), (C, E), (B, C)\)$
第 (2) 问解析¶
- 结论:图 \(G\) 的 MST 是唯一的。
- 理由证明:
- 图 \(G\)$ \text{共有 5 个顶点,任何生成树均恰好包含} $\(5 - 1 = 4\) 条边。
- 在全图的所有边中,权值最小的 4 条边依次是:\((A, D) = 4, (D, E) = 4, (C, E) = 5, (B, C) = 5\)。
- 这 4 条最小边之间完全不构成任何简单回路,它们恰好构成一棵合法的生成树,总权值达到理论绝对下界: $\(W_{\min} = 4 + 4 + 5 + 5 = 18\)$
- 图中其余未被选入的所有边(权值均为 6),其权值均严格大于生成树中各边的权值。若尝试用任何一条权值为 6 的边替换掉当前的树边,生成树的总权值必严格大于 18。
- 因此,该图不存在任何其他等价的最小生成树,其 MST 具有唯一性。
第 (3) 问解析¶
本小问考查 MST 唯一的理论条件(题目明确要求给出“充分条件”): * 标准答案(强充分条件,阅卷基准点): 当带权连通图中所有边的权值互不相等(各不相同)时,其 MST 是唯一的。 * 更精细的充分条件(弱充分条件,同样给满分): 当带权连通图的任意一个简单回路中所包含的边的权值均不相同时(或每个回路中权值最大的边只有一条),其 MST 是唯一的。 * 评分细则解读: 1. 若考生回答“所有边的权值各不相同”,直接给满分(2分)。 2. 若考生回答“任意回路中各边权值均不相同”,给满分(2分)。 3. 若考生给出的条件人为限制了图的规模或形态(例如“图中顶点数小于 3 个”、“图中没有环”等),限制了通用性,最高只给 1 分。
四、 核心解题套路及易错陷阱¶
1. Prim 算法手算核心陷阱:割边遗忘症¶
- 高频易错现象:在草稿纸上手算 Prim 算法时,考生极易在加入新顶点 \(v_k\) 后,只盯着“新顶点发出的边”,而遗忘了“之前已经入树的老顶点发出的候选边”!
- 标准避坑操作规范——双集合边界划定法:
- 始终在草稿纸上划分两列:左侧为 \(S\)$ \text{(已入树),右侧为} $\(V \setminus S\)(未入树)。
- 每一轮选择边时,必须横向审视从左侧所有顶点连向右侧的所有边中的最小值。
- 借助辅助表格记录每个未入树顶点的
lowcost,每次只用新入树顶点更新未入树顶点的那一行,绝不漏看历史割边。
2. Kruskal 算法手算核心陷阱:跨分量盲目选边¶
- 高频易错现象:边权排序后,顺次选边时,只注意两端点是否曾经出现过,若看到端点曾经选过就误以为成环;或者没有识别出多条边在宏观上串成的大环。
- 标准避坑操作规范——连通分量染色法:
- 拿到题目,先在图边上标出全局非降序序号:\(e_1 \le e_2 \le e_3 \le \dots\)。
- 选边时,对端点进行分量染色(标记相同的数字)。若边的两端数字相同,则必成环,果断打叉跳过;若两端数字不同,连线并将两区域染为相同颜色。
- 一旦成功选出 \(n - 1\) 条边,立即停笔交卷,切勿继续遍历剩余边。
3. MST 唯一性命题真伪判断准则¶
408 选择题常在此设置逻辑陷阱,必须牢记以下命题判断法则: 1. “所有边权互不相同 \(\implies\) MST 唯一”:命题正确(充分条件)。 2. “MST 唯一 \(\implies\) 所有边权互不相同”:命题错误(非必要条件)。反例:同权边只要不构成环,MST 依然唯一。 3. “存在权值相同的边 \(\implies\) MST 不唯一”:命题错误。反例同上。 4. “无论 MST 是否唯一,所有 MST 的边权序列完全相同”:命题正确(边权多重集唯一性定理)。 5. “无论 MST 是否唯一,所有 MST 的总权值之和严格唯一”:命题正确。
4. 计算机网络 TTL 逐跳递减计算规范¶
与网络原理跨学科结合时,关于“H2 能否收到 IP 分组”的判定计算标准: 1. 跳数及路由器数统计: * 设源主机直连路由器 \(R_1\)$ \text{,目的主机直连路由器} $\(R_k\)。 * 路径包含的路由器序列为 \(R_1 \to R_2 \to \dots \to R_k\)$ \text{,共有} $\(k\)$ \text{个路由器,包含} $\(k - 1\) 条跨路由器链路。 2. TTL 逐跳审查: * 主机发送分组时设置初值 \(\text{TTL} = T\)。 * 进入 \(R_1\)$ \text{,转发前} $\(\text{TTL} \leftarrow T - 1\); * 经过 \(m\)$ \text{次路由器转发后,在第} $\(m\)$ \text{个路由器转发时的} $\(\text{TTL} = T - m\)。 * 若在某一中间路由器准备转发时 \(\text{TTL} \le 0\),则该路由器丢弃分组,无法送达。 * 充要判断式:若从源路由器到目的路由器的转发跳数(即途经需要执行减 1 操作的路由器数量)不超过初始 TTL,则能够送达;若超过,则中途耗尽丢弃。
五、 考点速记清单¶
- 基本性质:\(n\)$ \text{个顶点的连通图,其生成树必有且仅有} $\(n - 1\) 条边;最小生成树权值总和绝对唯一,但拓扑形态不一定唯一。
- 算法核心:Prim 算法以顶点为中心(加点法,贯彻割定理);Kruskal 算法以边权为中心(加边法,贯彻回路定理)。
- 选型法则:稠密图(边多)首选 Prim 算法(\(O(|V|^2)\)$ \text{,与边数无关);稀疏图(边少)首选 Kruskal 算法(} $\(O(|E| \log |V|)\),主要开销在边排序)。
- 并查集避圈:Kruskal 算法利用并查集判环;
Find查代表元,若两端点根相同则必成环舍弃,若不同则选入并Union合并。 - 唯一性判定:边权各不相同是 MST 唯一的充分非必要条件;任意环中各边权值不同是更优的充分条件;存在等权边不代表 MST 不唯一。
- 边权守恒:同一个图的不同 MST 中,每种特定权值的边数分布完全相同,差异仅在等权边的拓扑替换。
- 与最短路径区分:MST 追求全局总权值最小,SSSP 追求源点到各点累加距离最小;MST 上的路径不一定是最短路径;Prim、Kruskal 均不能求单源最短路径。
- BFS 求最短路径:仅当所有边权均为 1(或所有边权相等)时,BFS 搜索树才严格等价于单源最短路径树。
- 网络 TTL 联动:IP 分组每经过一台路由器转发,首部 TTL 严格减 1;TTL 减至 0 时立即丢弃并触发 ICMP 超时,不再转发。
- 手算规范:Prim 算割边,看清已选全集合与未选全集合的交界;Kruskal 先排序,选满 \(n - 1\) 条边即收工。