Prim 算法

2026 大纲 五（四）图的基本应用 1. 最小（代价）生成树 · 加点法（加边法见《Kruskal》）。本篇同时承载 MST 的定义、割性质与唯一性判据。

用最小的总造价把所有点连起来

问题原型是这样的：$n$ 个城市要建通信网，任意两城之间的线路造价已知，怎么连才能让所有城市互通且总造价最小？

"互通"要求结果是连通的；"总造价最小"要求不能有多余的边——多一条边就多一份钱，而连通 $n$ 个顶点最少只要 $n-1$ 条边。恰好含全部顶点、恰好 $n-1$ 条边、无回路的连通子图，就是图的基本概念里讲过的生成树。

所有生成树里各边代价之和最小的那一棵，叫最小生成树（MST）。由定义直接就能读出三条：

• 含全部 $n$ 个顶点、恰有 $n-1$ 条边；
• 不含回路；
• 图必须连通才存在 MST，否则只有最小生成森林。

割性质：贪心为什么不会选错

Prim 和 Kruskal 都是贪心算法，而它们的正确性来自同一条性质：

🔴 割性质（MST 性质）：设 $U$ 是顶点集 $V$ 的一个非空真子集，若 $(u,v)$ 是跨越 $U$ 与 $V-U$ 的最小边（$u\in U,v\in V-U$），则必存在一棵包含 $(u,v)$ 的 MST。

证明（反证）。假设任何一棵 MST 都不含 $(u,v)$。取任意一棵 MST $T$，把 $(u,v)$ 加进去——树上任意两点间已有唯一路径，再加一条边必成环，所以 $T$ 中出现一个包含 $(u,v)$ 的回路。

这个回路起于 $U$ 内、终于 $U$ 内，中途去过 $V-U$，所以它上面必然还有另一条跨越边 $(u^{\prime },v^{\prime })$。删去 $(u^{\prime },v^{\prime })$ 打断回路，仍得一棵含全部顶点的生成树 $T^{\prime }$，且

$$w(T^{\prime })=w(T)+w(u,v)-w(u^{\prime },v^{\prime })$$

由于 $(u,v)$ 是所有跨越边中最小的，$w(u,v)\le w(u^{\prime },v^{\prime })$，故 $w(T^{\prime })\le w(T)$。又 $T$ 已经最小，所以 $w(T^{\prime })=w(T)$，即 $T^{\prime }$ 也是一棵 MST，而它含 $(u,v)$——与假设矛盾。∎

⚠️ 措辞要抠：结论是"存在一棵包含它的 MST"，不是"所有 MST 都包含它"。这个措辞上的松紧，正是后面"MST 可能不唯一"的根源，也是真题设错误选项的地方。

加点法：每轮拉一个最近的顶点进来

Prim 就是在反复使用割性质：把已并入的顶点集看作 $U$，每轮选"连接 $U$ 与 $V-U$ 的最小边"。共选 $n-1$ 轮。

它的中间状态始终是一棵连通的树——这是它与 Kruskal 最直观的区别（Kruskal 的中间状态是若干棵互不相连的树）。

实现要两个辅助数组，必须同步更新：

• lowcost[j] = 顶点 $j$ 到集合 $U$ 的最小边权（回答"多少"）
• closest[j] = 取到该最小值的那个 $U$ 中顶点（回答"接在哪"）

先动手看一眼

加载可视化中...

盯 lowcost 那一行怎么变：它量的是"到整棵树的距离"，不是"到起点的距离"。这个区别是下面最要紧的一处代码细节。

算法实现

#define INF 0x3f3f3f3f      // 无边填 INF，且 INF+INF 不会溢出 int

// cost[][] 为无向网的邻接矩阵；从 v0 出发输出各条边，返回总权值；不连通返回 -1
int Prim(int cost[][MAXV], int n, int v0) {
    int lowcost[MAXV], closest[MAXV], visited[MAXV] = {0}, total = 0;

    for (int i = 0; i < n; i++) {     // 初始化：U = {v0}
        lowcost[i] = cost[v0][i];
        closest[i] = v0;
    }
    visited[v0] = 1;

    for (int i = 1; i < n; i++) {     // 还要并入 n-1 个顶点
        int min = INF, k = -1;                    // ① 选最小
        for (int j = 0; j < n; j++)
            if (!visited[j] && lowcost[j] < min) { min = lowcost[j]; k = j; }
        if (k == -1) return -1;       // V-U 全不可达 → 图不连通；漏判则下一行越界写

        visited[k] = 1;                           // ② 并入
        printf("(%d, %d) w=%d\n", closest[k], k, lowcost[k]);
        total += lowcost[k];

        for (int j = 0; j < n; j++)               // ③ 更新
            if (!visited[j] && cost[k][j] < lowcost[j]) {
                lowcost[j] = cost[k][j];   // 不累加，只取这一条边的权
                closest[j] = k;            // 两个数组必须一起改
            }
    }
    return total;
}

🔴 更新式不累加：写的是 lowcost[j] = cost[k][j]，不是 lowcost[k] + cost[k][j]。因为量的是"到树的距离"，只要有一条边搭上树就够了。一旦加上累加，它就变成了（错误的）最短路径算法——Dijkstra 与 Prim 的骨架几乎一样，唯一的实质差别就在这个式子累不累加。

另一种等价写法是省掉 visited[]、改用 lowcost[k] = 0 标记已并入。两种写法效果相同但不能混用：若既用 lowcost[k]=0 标记又不判 visited，下一轮选最小时会把 0 当成最小值反复选中同一个顶点。本篇统一用 visited[]。

复杂度 $O(n^2)$，与边数 $e$ 完全无关：外层循环 $n-1$ 次，每轮内部两次线性扫描（"选最小"扫 $V-U$ 是 $O(n)$，"更新"在邻接矩阵下必须扫 $k$ 的一整行也是 $O(n)$）。图上有 $n-1$ 条边还是 $n(n-1)/2$ 条边，耗时一样。这正是它适合稠密图的原因。

唯一性：本节最容易答错的地方

先把两件事分开：

🔴 MST 的总权值一定唯一（"最小"是图的固有量），但 MST 本身未必唯一——不同的边集可以达到同一个最小值。

真题把这一条拆成四个命题考过，四个里只有第一个对。逐个看：

"最小生成树的代价唯一"——对。 假设存在两棵 MST 总权不同，把权小的那棵里的某条边换进权大的那棵，能得到更小的生成树，与"已最小"矛盾。

"所有权值最小的边一定出现在所有 MST 中"——错。 准确表述要加"唯一"两个字：唯一的最小权值边一定在每棵 MST 中。若最小权值的边有多条且它们构成环，就可以挑环外的边，未必每条都入选。

"Prim 从不同顶点开始得到的 MST 一定相同"——错。 存在等权边时，Prim 选"下一条最小边"会遇到并列，不同起点做出的选择不同。最小反例：正方形四个顶点、四条边权全为 1，从不同的角出发得到不同的"L 形" MST。

"Prim 和 Kruskal 得到的 MST 总不相同"——错，而且错得更彻底。 若所有边权互不相同，MST 唯一，两个算法必然给出同一棵。

那么什么时候唯一？真题直接问过这条：

🔴 边权互不相同 $\Rightarrow$ MST 唯一。 这是充分非必要条件，答题写这一句就够。

证明（反证）：若 MST 不唯一，存在两棵不同的 MST $T_1$、$T_2$。取它们对称差中权值最小的边 $e$，不妨设 $e\in T_1\setminus T_2$。把 $e$ 加入 $T_2$ 形成一个环 $C$，$C$ 中至少有一条不在 $T_1$ 的边 $e^{\prime }$。由于边权互不相同，要么 $w(e)<w(e^{\prime })$——用 $e$ 换 $e^{\prime }$ 让 $T_2$ 更轻，矛盾；要么 $w(e)>w(e^{\prime })$——用 $e^{\prime }$ 换 $e$ 让 $T_1$ 更轻，同样矛盾。∎

⚠️ 反过来不成立："图里有等权边"推不出"MST 不唯一"。判断时不要只看"有没有权值相同的边"，要看某一轮里有没有两条同权、且当时两端分属不同连通块的边——只有这种真正的并列才制造多解。下面的走查里有个现成的反例：一张图有三条权为 5 的边，MST 却是唯一的。

六顶点无向网的逐轮推演（想手动模拟一遍就展开）

10 条边：$A-B$ 6、$A-C$ 1、$A-D$ 5、$B-C$ 5、$B-E$ 3、$C-D$ 5、$C-E$ 6、$C-F$ 4、$D-F$ 2、$E-F$ 6。

从 $A$ 出发。表中每格写"lowcost(closest)"，— 表示该顶点已并入 $U$：

轮次	$U$	B	C	D	E	F	选中顶点	选中的边
初始	$\{A\}$	6(A)	1(A)	5(A)	∞(A)	∞(A)	C	$(A,C)$ 权 1
1	$\{A,C\}$	5(C)	—	5(A)	6(C)	4(C)	F	$(C,F)$ 权 4
2	$\{A,C,F\}$	5(C)	—	2(F)	6(C)	—	D	$(F,D)$ 权 2
3	$\{A,C,F,D\}$	5(C)	—	—	6(C)	—	B	$(C,B)$ 权 5
4	$\{A,C,F,D,B\}$	—	—	—	3(B)	—	E	$(B,E)$ 权 3

逐轮的更新解释（这是手算最容易漏的一步）：

• 并入 C 之后：$B$ 原本挂 $A$ 要 6，挂 $C$ 只要 5，更新为 5(C)；$D$ 挂 $A$ 要 5、挂 $C$ 也要 5，不是严格小于，不更新，仍是 5(A)；$E$ 从 ∞ 变 6(C)；$F$ 从 ∞ 变 4(C)。
• 并入 F 之后：$D$ 挂 $F$ 只要 2，更新为 2(F)；$E$ 挂 $F$ 要 6，与原来的 6(C) 相等，不更新。
• 并入 D 之后：$D$ 与 $B$、$E$ 都没有边，无更新。
• 并入 B 之后：$E$ 挂 $B$ 只要 3，更新为 3(B)。

结果：5 条边 $(A,C),(C,F),(F,D),(C,B),(B,E)$，总权值 $1+4+2+5+3=\mathbf{15}$。

自检：边数 $=5=n-1$ ✓；含全部 6 个顶点 ✓；无回路 ✓。三条中任一条不满足，就说明前面某一轮算错了。

这张图有三条权为 5 的边（$A-D$、$B-C$、$C-D$），MST 却唯一——因为其中只有 $B-C$ 在关键时刻是唯一可选的跨越边，另外两条被考虑时两端已经连通了。这就是"有等权边推不出不唯一"的现成反例。真正会造出多棵 MST 的是三角形 $A-B=1,B-C=1,A-C=1$：任取两条边都是权值为 2 的 MST，共 3 棵。

图注：六个快照 (a)→(f) 是 Prim 从顶点 0 出发逐轮生长的样子。注意每一步都只多出一个顶点和一条边，而且已选中的部分始终是连通的一棵树——这是 Prim 与 Kruskal 最直观的区别。 图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.18 用 Prim 算法构造最小生成树的过程，p374

不跑算法直接判某条边在不在 MST 里（遇到这类判断题时展开）

有了割性质（Prim 的依据）与环性质（Kruskal 的依据），不必真跑一遍算法：

规则	结论	依据
某边是跨越某个割的唯一最小边（严格小于其他跨越边）	必定属于每一棵 MST	割性质；若不含它，交换后总权严格变小，矛盾
某边是某个回路上的唯一最大边（严格大于回路上其他边）	必定不属于任何 MST	环性质
全图权值最小的边（若唯一）	必定属于 MST	它是"以它一端为 $U$"这个割的唯一最小跨越边
全图权值最大的边（若唯一）且它在某个回路上	必定不属于 MST	它是那个回路上的唯一最大边

用上面走查那张图检验：

• $A-C$ 权 1 是全图唯一最小边 → 必在 MST 中 ✓。
• $A-D$ 权 5 在回路 $A-C-F-D-A$（权 $5,1,4,2$）上是唯一最大边 → 必不在任何 MST 中 ✓。
• $A-B$ 权 6 在回路 $A-B-C-A$（权 $6,5,1$）上也是唯一最大边 → 必不在 MST 中 ✓。

注意"唯一"两个字：若最大边并列，只能说"这些并列的边不可能全部入选"，不能断定某一条一定落选。

堆优化版的复杂度来历，以及 Prim 与 Kruskal 的选型代数

堆优化 $O(e\log n)$：把"选最小"换成从最小堆取，"更新"换成对每条边做一次堆内调整。每条边最多一次 $O(\log n)$ 调整、每个顶点最多一次 $O(\log n)$ 取出，合计 $O((n+e)\log n)=O(e\log n)$（连通图有 $e\ge n-1$）。

指标	朴素（邻接矩阵）	堆优化（邻接表 + 最小堆）
时间	$O(n^2)$	$O(e\log n)$
空间	辅助 $O(n)$，图本身 $O(n^2)$	辅助 $O(n)$，图本身 $O(n+e)$
适合	稠密图	稀疏图

选型要代数算，不能凭感觉：

• 稠密图 $e\approx n^2$：Kruskal 的 $O(e\log e)$ 退化成 $O(n^2\log n^2)=O(n^2\log n)$，Prim 的 $O(n^2)$ 更快。
• 稀疏图 $e\approx n$：Kruskal 是 $O(n\log n)$，远小于 Prim 朴素版的 $O(n^2)$，Kruskal 更快。

Prim vs Kruskal，以及 MST vs 最短路径树

一组概念	差别	判别依据
Prim vs Kruskal	加点（中间状态是一棵树）vs 加边（中间状态是森林）	看中间过程连不连通：Prim 的已选边始终连成一片
MST vs 最短路径树	最小化总权和 vs 最小化各点到源点的距离	两者一般不是同一棵树

第二行值得单独举例，因为真题正面考过：三角形 $A-B=1$、$B-C=1$、$A-C=1.5$，MST 是 $\{AB,BC\}$ 总权 2；但以 $A$ 为源点时 $A\to C$ 的最短距离是 $1.5$（直连），而 MST 上 $A$ 到 $C$ 要走 $1+1=2$。

🔴 MST 保证"总造价最小"，不保证"任意两点之间走得最近"。 所以给一个各边权均为 1 的连通图，问"能求出某顶点到其余各顶点最短路径的是 Prim / Kruskal / BFS 中的哪些"，答案只有 BFS——权全相等也救不了 MST，因为两者优化的目标本来就不同。

考点速记

三条结论：

1. 割性质是 Prim 与 Kruskal 共同的正确性来源：跨越任意割的最小边，必属于某棵 MST。
2. 朴素 Prim 是 $O(n^2)$、与边数无关，适合稠密图；lowcost 存的是"到树的距离"，更新时不累加。
3. MST 的总权值唯一，MST 本身未必唯一；边权互不相同 $\Rightarrow$ 唯一，反过来不成立。

这一节在真题里被考过的形式（下方「真题练习」逐题对应）：

• 依次给出算法选出的边（大题第 1 问）：从指定顶点开始，按轮次写出每一轮并入的边。画 lowcost/closest 表逐轮填，比在图上目测稳得多。
• MST 是否唯一 + 唯一的充分条件（大题第 2、3 问）：第 2 问要对着具体的图判；第 3 问答"当图中所有边的权值互不相同时，MST 一定唯一"即可，不必给更精确的等价条件。
• 四个 MST 命题的真伪判断：代价唯一（对）、所有最小权边都在所有 MST 中（错，要加"唯一"）、Prim 从不同起点结果一定相同（错）、Prim 与 Kruskal 结果总不相同（错）。
• Prim 与 Kruskal 第 $k$ 次选边的对比：问"可能是 Kruskal 第 2 次选中、但不是 Prim（从某顶点开始）第 2 次选中的边"。两个算法各跑两步分别列出候选，再取差集。注意 Prim 的起点是题目指定的，换个起点答案就变。
• 枚举全部最经济方案（跨科目大题）：给一张城市光缆费用图，要求给出所有可能的最小方案并算总费用；同题还会问"该图可采用哪种存储结构"和"求解用什么算法名称"。
• 能不能用来求最短路：作为错误选项出现——MST 不是最短路径树。

易错："存在一棵包含它的 MST" ≠ "所有 MST 都包含它"。 割性质的措辞是前者；要断言某条边在每一棵 MST 里，得加"唯一最小"这个条件。

易错：有等权边推不出 MST 不唯一。 三条权相同的边照样可以各自处在"非选不可"的位置。要看某一轮里有没有真正并列的可选跨越边。

易错：lowcost 的更新式不累加。 累加就变成了 Dijkstra 的松弛式，求出来的是最短路径树而不是最小生成树。

易错："选最小"时要判 k == -1。 图不连通时 $V-U$ 里全是 $\mathrm{\infty }$，选不出顶点；漏了这一判会越界写数组。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p165，§6.6.1： 最小生成树的引入（$n$ 个城市建通信网，"连通 $n$ 个城市只需要 $n-1$ 条线路"）， 以及 MST 性质的表述——"假设 $N=(V,E)$ 是一个连通网，$U$ 是顶点集 $V$ 的一个非空子集。 若 $(u,v)$ 是一条具有最小权值（代价）的边，其中 $u\in U$，$v\in V-U$， 则必存在一棵包含边 $(u,v)$ 的最小生成树"，并在同页起用反证法给出证明。
• 同书印刷 p166：证明的后半段（删去回路上的另一条跨越边 $(u^{\prime },v^{\prime })$ 得到 $T^{\prime }$， 由 $(u,v)$ 权值不高于 $(u^{\prime },v^{\prime })$ 推出矛盾）；同页给出普里姆算法的三步构造过程， 并指出"普里姆算法逐步增加 $U$ 中的顶点，可称为加点法"， 以及"每次选择最小边时，可能存在多条同样权值的边可选，此时任选其一即可"。
• 同书印刷 p166：辅助数组 closedge 的定义——每个 $v_i\in V-U$ 对应一个分量， 含 lowcost（最小边上的权值）与 adjvex（最小边在 $U$ 中的那个顶点）两个域， 即本篇的 lowcost[] 与 closest[]。

图源：殷人昆《数据结构——用面向对象方法与 C++ 描述》（第 2 版）图8.18，p374。

相关知识

Kruskal 算法（同一条大纲下的加边法，适合稀疏图）｜ Dijkstra 算法（骨架相同，差别只在松弛式是否累加）｜ 图的基本概念（生成树的定义与"$n-1$ 条边"的来历）｜ 邻接矩阵（朴素实现的存储前提）｜ 堆（堆优化用它维护 lowcost 的最小值）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• Floyd 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习

相关真题（5题）

2023Q62分2018Q4212分2017Q428分2015Q62分2012Q82分