考研全科复习资料

408

数据结构

最小生成树（Prim/Kruskal）

一、定位信息

圈层：核心层（大纲考点）
前置知识：图的基本概念（连通图、生成树、权/网）、图的存储（邻接矩阵/邻接表）、并查集（Kruskal 算法需要）。
知识网络定位：最小生成树是图论中的经典优化问题，建立在图的连通性和权值基础上，是贪心算法思想在图论中的典型应用。
考点热度：H级（高频重点） — 近 5 年真题中出现 ≥3 次，常以手算执行过程或算法对比的形式出现，单次分值 5–8 分。

二、知识点讲解

2.1 最小生成树的定义

给定一个连通无向网 $G = (V, E)$ ，每条边 $(u, v)$ 有权值 $w(u, v)$ 。 $G$ 的最小生成树（Minimum Spanning Tree, MST）是一棵包含 $G$ 中所有顶点的树，且树中所有边的权值之和最小。

关键性质：

MST 有 $n$ 个顶点和 $n-1$ 条边。
MST 不一定唯一（当有权值相同的边时）。
最小生成树的 MST 性质：设 $U$ 是顶点集 $V$ 的一个非空真子集，若 $(u, v)$ 是 $u \in U, v \in V - U$ 的边中权值最小的边，则一定存在一棵 MST 包含边 $(u, v)$ 。

2.2 Prim 算法

核心思想：从一个顶点开始，每次选择连接"已选顶点集"和"未选顶点集"的最小权值边，将对应的未选顶点加入已选集，直到所有顶点都被选中。

算法步骤：

初始化：任选一个起始顶点 $u_0$ ，将 $u_0$ 加入顶点集 $U$ 。
在所有一端在 $U$ 中、另一端在 $V - U$ 中的边中，找权值最小的边 $(u, v)$ 。
将 $v$ 加入 $U$ ，将边 $(u, v)$ 加入 MST。
重复步骤 2–3，直到 $U = V$ （共加入 $n-1$ 条边）。

伪代码（邻接矩阵存储）：

cpp

void Prim(MGraph G, int start) {
    // 从顶点 start 出发构造最小生成树
    int lowcost[MAX_VERTEX_NUM];  // 存储各顶点到已选集合的最小边权值
    int adjvex[MAX_VERTEX_NUM];   // 存储各顶点对应的最小边的另一端
    
    for (int i = 0; i < G.vexnum; i++) {
        lowcost[i] = G.arc[start][i];  // 初始化：start 到各顶点的边权
        adjvex[i] = start;              // 初始都从 start 出发
    }
    lowcost[start] = 0;                 // start 已加入集合
    
    for (int i = 1; i < G.vexnum; i++) {
        // 需要再加入 n-1 个顶点
        int min = INF, k = -1;
        for (int j = 0; j < G.vexnum; j++) {
            // 找 lowcost 中最小的非零值
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;                  // k 是当前离已选集合最近的顶点
            }
        }
        printf("加入边 (%d, %d)，权值 %d\n", adjvex[k], k, min);
        lowcost[k] = 0;                 // k 加入已选集合
        
        for (int j = 0; j < G.vexnum; j++) {
            // 更新 lowcost：k 的加入可能带来更短的边
            if (G.arc[k][j] < lowcost[j]) {
                lowcost[j] = G.arc[k][j];
                adjvex[j] = k;
            }
        }
    }
}

时间复杂度： $O(n^2)$ （两层循环），适合稠密图。

2.3 Kruskal 算法

核心思想：将所有边按权值从小到大排序，依次考虑每条边，如果这条边连接的两个顶点属于不同的连通分量（不成环），则加入 MST。

算法步骤：

将图 $G$ 的所有边按权值升序排序。
初始化：每个顶点自成一个连通分量（用并查集维护）。
按排序顺序依次取边 $(u, v)$ $(u, v)$ ：
- 若 $u$ 和 $v$ 属于不同连通分量（Find(u) != Find(v)），则将该边加入 MST，合并两个分量（Union(u, v)）。
- 若 $u$ 和 $v$ 属于同一连通分量，跳过（否则会形成环）。
重复直到 MST 有 $n-1$ 条边。

伪代码：

cpp

void Kruskal(Graph G) {
    // 用并查集实现 Kruskal 算法
    Edge edges[MAX_EDGE];       // 存储所有边
    Sort(edges);                // 按权值升序排序，O(e log e)
    
    InitUnionFind(G.vexnum);    // 初始化并查集
    
    int count = 0;              // 已加入 MST 的边数
    for (int i = 0; i < G.edgeNum && count < G.vexnum - 1; i++) {
        int u = edges[i].u;     // 边的起点
        int v = edges[i].v;     // 边的终点
        int fu = Find(u);       // 找 u 所在集合的根
        int fv = Find(v);       // 找 v 所在集合的根
        if (fu != fv) {         // 若不在同一集合
            printf("加入边 (%d, %d)，权值 %d\n", u, v, edges[i].weight);
            Union(fu, fv);      // 合并两个集合
            count++;            // MST 边数加 1
        }
        // 若在同一集合，跳过（加入会成环）
    }
}

时间复杂度： $O(e \log e)$ （主要由排序决定），适合稀疏图。

2.4 Prim 与 Kruskal 完整执行示例

示例图：

【图示说明】无向连通网有 6 个顶点 $v_0, v_1, v_2, v_3, v_4, v_5$ 。边及权值： $(v_0,v_1,6), (v_0,v_2,1), (v_0,v_3,5), (v_1,v_2,5), (v_1,v_4,3), (v_2,v_3,5), (v_2,v_4,6), (v_2,v_5,4), (v_3,v_5,2), (v_4,v_5,6)$ 。

Prim 执行过程（从 $v_0$ 出发）：

步骤	已选集合 $U$	可选边（一端在 $U$ ，一端不在）	选中边	加入顶点	累计权值
初始	$\{v_0\}$	—	—	—	0
1	$\{v_0\}$	$(v_0,v_1,6), (v_0,v_2,1), (v_0,v_3,5)$	$(v_0,v_2,1)$	$v_2$	1
2	$\{v_0,v_2\}$	$(v_0,v_1,6), (v_0,v_3,5), (v_1,v_2,5), (v_2,v_3,5), (v_2,v_4,6), (v_2,v_5,4)$	$(v_2,v_5,4)$	$v_5$	5
3	$\{v_0,v_2,v_5\}$	$(v_0,v_1,6), (v_0,v_3,5), (v_1,v_2,5), (v_2,v_3,5), (v_2,v_4,6), (v_3,v_5,2), (v_4,v_5,6)$	$(v_3,v_5,2)$	$v_3$	7
4	$\{v_0,v_2,v_3,v_5\}$	$(v_0,v_1,6), (v_1,v_2,5), (v_2,v_4,6), (v_4,v_5,6)$	$(v_1,v_2,5)$	$v_1$	12
5	$\{v_0,v_1,v_2,v_3,v_5\}$	$(v_2,v_4,6), (v_4,v_5,6), (v_1,v_4,3)$	$(v_1,v_4,3)$	$v_4$	15

MST 边集： $(v_0,v_2,1), (v_2,v_5,4), (v_3,v_5,2), (v_1,v_2,5), (v_1,v_4,3)$ ，总权值 15。

Kruskal 执行过程：

边排序： $(v_0,v_2,1), (v_3,v_5,2), (v_1,v_4,3), (v_2,v_5,4), (v_0,v_3,5), (v_1,v_2,5), (v_2,v_3,5), (v_0,v_1,6), (v_2,v_4,6), (v_4,v_5,6)$

步骤	考虑边	端点集合	是否成环	操作	累计权值
1	$(v_0,v_2,1)$	$\{v_0\},\{v_2\}$	否	加入 MST	1
2	$(v_3,v_5,2)$	$\{v_3\},\{v_5\}$	否	加入 MST	3
3	$(v_1,v_4,3)$	$\{v_1\},\{v_4\}$	否	加入 MST	6
4	$(v_2,v_5,4)$	$\{v_0,v_2\},\{v_3,v_5\}$	否	加入 MST	10
5	$(v_0,v_3,5)$	$\{v_0,v_2,v_3,v_5\}$	是（同集合）	跳过	10
6	$(v_1,v_2,5)$	$\{v_1,v_4\},\{v_0,v_2,v_3,v_5\}$	否	加入 MST	15

MST 边集： $(v_0,v_2,1), (v_3,v_5,2), (v_1,v_4,3), (v_2,v_5,4), (v_1,v_2,5)$ ，总权值 15。（边集可能与 Prim 不同，但总权值相同。）

三、记忆与理解辅助

技巧 1：Prim vs Kruskal 对比表

对比维度	Prim 算法	Kruskal 算法
策略	从一个顶点出发，逐步扩展已选集合	从所有边中选最小的，不成环就加入
关注对象	顶点（每次加入一个顶点）	边（每次考虑一条边）
数据结构	数组（lowcost）	并查集 + 排序
时间复杂度	$O(n^2)$	$O(e \log e)$
适用场景	稠密图（ $e$ 接近 $n^2$ ）	稀疏图（ $e \ll n^2$ ）
实现难度	较简单	需要并查集

技巧 2：口诀

"Prim 选点，Kruskal 选边"
"Prim 稠密好，Kruskal 稀疏妙"
"不成环就加，成了环就跳"（Kruskal）

技巧 3：MST 唯一性判断

若图中所有边的权值互不相同，则 MST 唯一。
若有权值相同的边，MST 可能不唯一，但总权值一定相同。

四、例题与精解

例题 1（基础巩固）

题目：对下图所示的无向连通网，用 Kruskal 算法求最小生成树，写出选边过程。

【图示说明】4 个顶点 $v_0, v_1, v_2, v_3$ 。边及权值： $(v_0,v_1,1), (v_0,v_2,4), (v_0,v_3,3), (v_1,v_2,2), (v_2,v_3,5)$ 。

命题意图：考查 Kruskal 算法的基本执行过程。

审题分析：4 个顶点、5 条边，需要选 3 条边构成 MST。

完整步骤：

排序所有边： $(v_0,v_1,1), (v_1,v_2,2), (v_0,v_3,3), (v_0,v_2,4), (v_2,v_3,5)$ 。
初始化并查集： $\{v_0\}, \{v_1\}, \{v_2\}, \{v_3\}$ 。
考虑 $(v_0,v_1,1)$ ： $v_0$ 和 $v_1$ 不同集合，加入。合并为 $\{v_0,v_1\}$ 。MST 边数 = 1。
考虑 $(v_1,v_2,2)$ ： $v_1$ 和 $v_2$ 不同集合，加入。合并为 $\{v_0,v_1,v_2\}$ 。MST 边数 = 2。
考虑 $(v_0,v_3,3)$ ： $v_0$ 和 $v_3$ 不同集合，加入。合并为 $\{v_0,v_1,v_2,v_3\}$ 。MST 边数 = 3 = $n-1$ ，停止。

MST： $(v_0,v_1,1), (v_1,v_2,2), (v_0,v_3,3)$ ，总权值 = 6。

方法反思：Kruskal 的关键是排序 + 判环（并查集）。变式：如果权值相同的边有多条，需要分析 MST 是否唯一。

例题 2（中等提升）

题目：证明：对于连通无向网，若所有边的权值互不相同，则最小生成树唯一。

命题意图：考查对 MST 性质的理解和反证法思维。

审题分析：

已知：连通无向网，所有边权值互不相同。
求证：MST 唯一。

解题思路：反证法。假设存在两棵不同的 MST，推导矛盾。

完整步骤：

假设存在两棵不同的最小生成树 $T_1$ 和 $T_2$ ，且它们的总权值相等。
设 $e$ 是属于 $T_1$ 但不属于 $T_2$ 的权值最小的边。
将 $e$ 加入 $T_2$ ，必然形成一个环（因为 $T_2$ 本身是树，加一条边必成环）。
该环中必然存在一条边 $e'$ 属于 $T_2$ 但不属于 $T_1$ （否则 $T_1$ 中也有环，矛盾）。
由于所有边权值互不相同， $w(e) \neq w(e')$ $w (e) \neq = w (e^{'})$ 。
- 若 $w(e) < w(e')$ ：将 $T_2$ 中的 $e'$ 替换为 $e$ ，得到一棵权值更小的生成树，与 $T_2$ 是 MST 矛盾。
- 若 $w(e) > w(e')$ ：由于 $e$ 是 $T_1$ 中不在 $T_2$ 中的最小权边，而 $e' \notin T_1$ 且 $w(e') < w(e)$ ，这与 $e$ 的选取矛盾。
两种情况都矛盾，故假设不成立，MST 唯一。 $\square$

方法反思：此证明使用了 MST 的"环性质"——MST 中加入任何一条非树边都会形成环，且该非树边的权值是环中最大的。这个性质本身也常作为选择题考点。

五、考情分析

考查频次：近 5 年真题中出现 ≥3 次。
常见题型：选择题（算法对比、MST 唯一性判断）、综合应用题（手算 Prim/Kruskal 执行过程）。
分值占比：选择题 2 分，综合题 5–8 分。
命题趋势：手算 Prim/Kruskal 执行过程是高频题型，近年也出现过要求写伪代码的题目。MST 的性质证明偶尔出现在选择题中。
基于大纲与命题规律推测

六、易错点提醒

错误表现：Prim 算法中，更新 lowcost 时没有用新加入顶点的边权来更新，导致结果错误。 错误原因：每加入一个新顶点 $k$ ，必须用 $k$ 到其他顶点的边权来更新 lowcost（取更小值），否则无法保证选到全局最小边。 正确做法：每次加入顶点后，立即执行 lowcost[j] = min(lowcost[j], G.arc[k][j])。
错误表现：Kruskal 算法中，忘记检查是否成环，直接按顺序加入所有边。 错误原因：贪心策略必须保证每次加入的边不形成环，否则得到的不是树。 正确做法：用并查集判断两个端点是否在同一集合，不同集合才加入。
错误表现：认为 Prim 和 Kruskal 得到的 MST 一定相同（边集相同）。 错误原因：当有权值相同的边时，两种算法可能选择不同的边，但总权值一定相同。 正确理解：MST 的总权值唯一，但边集可能不唯一（权值相同时）。
错误表现：Kruskal 算法时间复杂度写成 $O(e^2)$ 。 错误原因：排序用 $O(e \log e)$ 而非 $O(e^2)$ ；并查集操作接近 $O(1)$ 。 正确做法：Kruskal 时间复杂度 = 排序复杂度 $O(e \log e)$ + 并查集操作 $O(e \cdot \alpha(n))$ ，整体 $O(e \log e)$ 。

七、来源标注

依据 2026 考研统考大纲
依据《数据结构（C语言版）》严蔚敏版
依据大学本科经典教材共识

408 ​

数据结构 ​

最小生成树（Prim/Kruskal） ​

一、定位信息 ​

二、知识点讲解 ​

2.1 最小生成树的定义 ​

2.2 Prim 算法 ​

2.3 Kruskal 算法 ​

2.4 Prim 与 Kruskal 完整执行示例 ​

三、记忆与理解辅助 ​

四、例题与精解 ​

例题 1（基础巩固） ​

例题 2（中等提升） ​

五、考情分析 ​

六、易错点提醒 ​

七、来源标注 ​

408