Appearance
最小生成树：Prim 与 Kruskal
概念
生成树是连通图的极小连通子图，含全部 n 个顶点、n − 1 条边。最小生成树（Minimum Spanning Tree, MST）则是边权之和最小的那棵生成树。
一句话理解：要在 n 个城市之间修公路让它们全部连通，每条候选路有造价，MST 就是"总造价最低的连通方案"。它一定是一棵树——恰好 n − 1 条路，多一条就出现环（白花钱），少一条就不连通。
三条基本事实：
- MST 一定存在（只要原图连通），且一定是原图的极小连通子图；
- MST 的边权之和是唯一的，但 MST 本身未必唯一（存在权值相等的边时可能有好几棵）；
- MST 有 n − 1 条边，不管图有多少条边。
原理
构造思想：贪心
两种经典算法都基于同一个切割性质（Cut Property）：
把顶点集任意切成两半，横跨这个切割的最小权值边必定在某棵 MST 中。
由此得到两条等价的操作路线：
| Prim（普里姆） | Kruskal（克鲁斯卡尔） | |
|---|---|---|
| 别名 | 加点法 | 加边法 |
| 维护对象 | 一个顶点集合 U（已长好部分树的连通块） | 一个森林（若干连通分量） |
| 每步动作 | 找一条连接 U 与 V−U 的最小边，把新点收进 U | 取全局最小边，两端不同连通块就并入（合并森林） |
| 关键性质 | U 始终是一棵单棵树 | 中途是森林，最后合成一棵树 |
| 需要的数据结构 | lowcost[] / 优先队列 | 并查集（判环 + 合并） |
| 时间复杂度 | ||
| 适用 | 稠密图（e 接近 n²） | 稀疏图（e << n²） |
Prim 详细过程（数组版，
维护三个数组：
lowcost[v]：当前从 U 出发到达 v 的最小边权（若已在 U 中则记 0）；adjvex[v]：这条最小边的另一个端点（在 U 中的那一端）；- 每轮选出
lowcost最小的 v 并入 U，再用 v 的出边更新所有邻居的 lowcost。
Prim(G, start):
for v in V: lowcost[v] = w(start, v); adjvex[v] = start
U = {start}; lowcost[start] = 0
重复 n-1 次:
k = argmin{ lowcost[v] | v 不在 U } /* 扫一遍数组，O(n) */
U ∪= {k}; 累加 lowcost[k] 到答案
for 每个邻接点 j of k:
if j 不在 U 且 w(k,j) < lowcost[j]:
lowcost[j] = w(k,j); adjvex[j] = k /* 更新，O(TD(k)) */外层 n − 1 轮、每轮扫 n 个元素找最小值 →
用二叉堆优化后是
Kruskal 详细过程（并查集，
Kruskal(G):
把 e 条边按权值从小到大排序 /* O(e log e)，主导复杂度 */
初始化并查集：每个顶点自成一个集合
for (u, v, w) in 排序后的边:
if find(u) != find(v): /* 不在同一连通块 → 不会成环 */
union(u, v); 选入 MST; 累加 w
if 已选 n-1 条边: break**为什么这样就能判环？**因为并查集的 find 就完成了判环：两端已在同一集合说明它们已被前面的边连通了，再加就成环。
MST 的唯一性
先看什么情况下 MST 一定唯一：若所有边权互不相同，则 MST 唯一。出现相等权值时不保证唯一，但只要每次执行切割，相等的候选边"互换"不影响权和，权和仍唯一。
考点句式："该图的最小生成树不是唯一的，但其权值之和唯一。"
示例
沿用第 20、21 章那张图的拓扑（6 个顶点、7 条边），这次给每条边加上权值，求它的 MST。 边表：
(1,2)=6 (1,3)=1 (2,4)=5 (2,5)=3 (3,5)=7 (4,6)=2 (5,6)=6
6 5
1 ──────── 2 ──────── 4
│ ╲ │ ╲ │
│1 3 │ 5(2-5) │2
│ ╲│ ╲ │
3 ──────── 5 ──────── 6
7 6
边权一览：(1,2)=6 (1,3)=1 (2,4)=5 (2,5)=3 (3,5)=7 (4,6)=2 (5,6)=6方法一：Prim（从顶点 1 出发）
| 轮次 | 候选边（横跨 U 与 V−U） | 选中 | 加入后 U | 累计权值和 |
|---|---|---|---|---|
| 0 | — | 起点 1 | 0 | |
| 1 | (1,2)=6，(1,3)=1 | (1,3) | 1 | |
| 2 | (1,2)=6，(3,5)=7 | (1,2) | 7 | |
| 3 | (2,4)=5，(2,5)=3，(3,5)=7 | (2,5) | 10 | |
| 4 | (2,4)=5，(5,6)=6 | (2,4) | 15 | |
| 5 | (4,6)=2，(5,6)=6 | (4,6) | 17 |
第 3 轮注意：候选边 (2,5)=3 虽然比第 2 轮选的 (1,2)=6 小，但那时它还横跨不了切割（5 与 U 中的 2 同在集合外），所以只能在 U 扩到含 2 之后才能被考虑。这就是" Prim 只看当前横向切割"的含义。
MST 边集：{(1,3)=1, (1,2)=6, (2,5)=3, (2,4)=5, (4,6)=2}
权值之和 = 1 + 6 + 3 + 5 + 2 = 17方法二：Kruskal（按边权排序）
排序后：(1,3)=1, (4,6)=2, (2,5)=3, (2,4)=5, (1,2)=6, (5,6)=6, (3,5)=7
| 步 | 边 | 权 | 两端所在集合 | 决策 | 累计 |
|---|---|---|---|---|---|
| 1 | (1,3) | 1 | {1} 与 {3}，不同 | 选 | 1 |
| 2 | (4,6) | 2 | {4} 与 {6}，不同 | 选 | 3 |
| 3 | (2,5) | 3 | {2} 与 {5}，不同 | 选 | 6 |
| 4 | (2,4) | 5 | {2,5} 与 {4,6}，不同 | 选 | 11 |
| 5 | (1,2) | 6 | {1,3} 与 {2,5,4,6}，不同 | 选 | 17 |
| 6 | (5,6) | 6 | 6 与 5 同在 | 弃（成环） | 17 |
| 7 | (3,5) | 7 | 同上 | 弃（成环） | 17 |
已选满 n − 1 = 5 条边，结束。结果与 Prim 完全一致：权值和 17，边集相同。
唯一性检验：枚举全部"含 5 条边且能让 6 个点连通"的边集，权值恰为 17 的只有 1 个（上面的 Python 对照里就有这段枚举，输出 最小权和 = 17, MST 棵数 = 1），故本例 MST 唯一。
C 语言：Prim（数组版）+ Kruskal（并查集）
#include <stdio.h>
#include <stdlib.h>
#define MAXV 10
#define INF 0x3f3f3f3f
/* ---------- Prim：邻接矩阵，O(n^2) ---------- */
int g[MAXV][MAXV]; /* 权值矩阵，无边为 INF，主对角线 0 */
int prim(int n, int start) {
int lowcost[MAXV], adjvex[MAXV], inU[MAXV];
int i, j, k, total = 0;
for (i = 0; i < n; i++) {
lowcost[i] = g[start][i];
adjvex[i] = (g[start][i] < INF) ? start : -1;
inU[i] = 0;
}
inU[start] = 1;
for (int round = 1; round < n; round++) {
/* 找横跨切割的最小边 */
int min = INF; k = -1;
for (j = 0; j < n; j++)
if (!inU[j] && lowcost[j] < min) { min = lowcost[j]; k = j; }
if (k < 0) return -1; /* 图不连通，无 MST */
printf("选边 (%d,%d) 权 %d\n", adjvex[k] + 1, k + 1, min);
inU[k] = 1; total += min;
/* 用新顶点 k 更新 lowcost */
for (j = 0; j < n; j++)
if (!inU[j] && g[k][j] < lowcost[j]) {
lowcost[j] = g[k][j];
adjvex[j] = k;
}
}
return total;
}
/* ---------- Kruskal：边集数组 + 并查集 ---------- */
typedef struct { int u, v, w; } Edge;
Edge edges[MAXV * MAXV];
int parent[MAXV];
int find(int x) { while (parent[x] != x) x = parent[x] = parent[parent[x]]; return x; }
int kruskal(int n, int e, Edge es[]) {
int total = 0, cnt = 0;
for (int i = 0; i < n; i++) parent[i] = i; /* 已在 main 中排好序 */
for (int i = 0; i < e; i++) {
int ru = find(es[i].u), rv = find(es[i].v);
if (ru == rv) { printf("弃边 (%d,%d) 权 %d：成环\n", es[i].u + 1, es[i].v + 1, es[i].w); continue; }
parent[ru] = rv;
printf("选边 (%d,%d) 权 %d\n", es[i].u + 1, es[i].v + 1, es[i].w);
total += es[i].w;
if (++cnt == n - 1) break;
}
return cnt == n - 1 ? total : -1; /* -1 表示图不连通 */
}
static int cmp(const void *a, const void *b) {
return ((Edge *)a)->w - ((Edge *)b)->w;
}
int main(void) {
int n = 6;
int E[][3] = { {1,2,6}, {1,3,1}, {2,4,5}, {2,5,3}, {3,5,7}, {4,6,2}, {5,6,6} };
int e = sizeof(E) / sizeof(E[0]);
/* 建矩阵：顶点编号 1..6 映射到下标 0..5 */
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) g[i][j] = (i == j) ? 0 : INF;
for (int i = 0; i < e; i++) {
int u = E[i][0] - 1, v = E[i][1] - 1, w = E[i][2];
g[u][v] = g[v][u] = w;
edges[i].u = u; edges[i].v = v; edges[i].w = w;
}
printf("== Prim from 1 ==\n");
printf("MST 权值和 = %d\n\n", prim(n, 0)); /* 17 */
qsort(edges, e, sizeof(Edge), cmp);
printf("== Kruskal ==\n");
printf("MST 权值和 = %d\n", kruskal(n, e, edges)); /* 17 */
return 0;
}
c 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
Python 对照
E = [(1,2,6),(1,3,1),(2,4,5),(2,5,3),(3,5,7),(4,6,2),(5,6,6)]
n = 6
adj = {i: [] for i in range(1, n + 1)}
for u, v, w in E:
adj[u].append((v, w)); adj[v].append((u, w))
def prim(start=1):
"""加点法：每步选横跨 (U, V-U) 的最小边"""
U, tree, total = {start}, [], 0
while len(U) < n:
best = min((w, u, v) for u in U for v, w in adj[u] if v not in U)
w, u, v = best
tree.append((u, v, w)); U.add(v); total += w
return tree, total
def kruskal():
"""加边法：排序 + 并查集"""
p = {i: i for i in range(1, n + 1)}
def find(x):
while p[x] != x: p[x] = p[p[x]]; x = p[x]
return x
tree, total = [], 0
for u, v, w in sorted(E, key=lambda x: x[2]):
ru, rv = find(u), find(v)
if ru != rv:
p[ru] = rv; tree.append((u, v, w)); total += w
return tree, total
print("Prim :", prim()) # ([(1,3,1),(1,2,6),(2,5,3),(2,4,5),(4,6,2)], 17)
print("Kruskal:", kruskal()) # (排序后遍历的结果，权和同为 17)
# 唯一性检验：枚举所有 n-1 条边的连通子集
import itertools
ok = []
for comb in itertools.combinations(E, n - 1):
p = {i: i for i in range(1, n + 1)}
def find(x):
while p[x] != x: p[x] = p[p[x]]; x = p[x]
return x
good = True
for u, v, w in comb:
if find(u) == find(v): good = False; break
p[find(u)] = find(v)
if good: ok.append(comb)
best = min(sum(c[2] for c in cb) for cb in ok)
print("最小权和 =", best, " 达到最小值的 MST 棵数 =",
sum(1 for cb in ok if sum(c[2] for c in cb) == best)) # 17 1
python 本站为静态站，不提供在线运行；可复制到本地用 gcc / python 执行
考点
考点
1. 必背结论
- MST 含 n − 1 条边；权值和唯一，MST 本身未必唯一（有等权边时）。
- 所有边权互不相同 → MST 唯一。
- Prim 数组版
- Kruskal
- 两者都基于切割性质，都是贪心，得到的权和相同。
- Prim 过程中的 U 始终连通且是一棵树；Kruskal 中途是森林。
2. 解题套路
- 手算 Prim：画一张表，每轮列出所有横跨 U 与 V−U 的边再取最小，别凭直觉挑全局最小边——那是 Kruskal。
- 手算 Kruskal：先把边排好序，逐条判是否同集合，开始就得 n − 1 条为止。
- 判 MST 是否唯一：把所有 MST 可能被替换的边标出来，看是否存在等权边导致可互换。
3. 易错点
- Prim 与 Dijkstra 混淆：Prim 的 lowcost 是"到集合 U 的最小边"，Dijkstra 的 dist 是"到源点的最短距离"，更新式子一个是取最小边、一个是累加。二者形式上极像但不是一回事。
- Prim 的 lowcost 更新必须在新点并入之后立即做，且只更新不在 U 中的邻居；漏了更新条件会出错。
- 图不连通时不存在 MST（只有生成森林）。Prim 数组版里表现为"找不到 k（全是 INF）"，Kruskal 里表现为"选不够 n − 1 条边"。
- 认为 MST 一定唯一。反例：正方形的四条边权值全为 1，任取三条都是 MST，共 4 棵。
- 复杂度记错：Kruskal 的
- 顶点数 n 与边数 e：Prim 的数组版是
小结
- MST 是连通带权图的"最小代价连通方案"，n − 1 条边，权和唯一。
- Prim 加点（
- 手工是两个算法一次铺垫一张表：Prim 表看"横跨切割的边"，Kruskal 表看"排序后的边 + 是否同集合"。
- MST 唯一性看有没有等权边可互换。
- 下一步：MST 解决"连通全部顶点的最小代价"，而最短路径解决"两点之间最快怎么走"。
评论（0）
当前浏览器不允许本地存储，评论无法保存。
还没有评论，来说两句。