Olverae Assets

1 一句话定义

最小生成树（MST）就是在一张带权连通图里，挑出一组边把所有顶点连成一棵树（无环），并让这些边的权重之和最小。

把它想成给一片村庄铺水管：每对村庄之间铺管的造价（权重）不同，你要让所有村庄都通上水，又花最少的钱。显然不能铺成环（多余的管子白花钱），最后正好用 顶点数−1 条管子把大家连成一棵树——这棵最省钱的树就是最小生成树。

这正是下一节交互区的图（5 个顶点）。绿色的 4 条边把所有顶点连成一棵树、总权重最小（=16）；灰色虚线的边权重更大或会造成环，被舍弃。下一节你将用 Kruskal 一条条把它们选出来。

2 模型 · Kruskal：从最便宜的边开始，不成环就要

Kruskal 的思路特别朴素：把所有边按权重从小到大排队，一条条看——只要它不和已选的边成环，就收下。点 ▶ 看绿边怎么一条条长出来、哪些边因为"会成环"被划掉。

Kruskal 算法骨架（排序 + 并查集判环）

核心是用「并查集」O(1) 判断一条边的两端是否已经连通（连通了再加就成环）。

// 并查集 DSU：判断两端是否已连通、把两个集合并起来
int  parent[V];
void dsuInit(void)       { for (int i = 0; i < V; i++) parent[i] = i; } // 各自成集
int  find(int x)        { while (parent[x] != x) x = parent[x]; return x; } // 找代表
void unite(int a, int b) { parent[find(a)] = find(b); } // 合并（不能叫 union——C 关键字！）

// Kruskal 主干：排序 + 逐条判环（edges[i] = {u, v, w}）
int kruskal(Edge edges[], int m) {
    qsort(edges, m, sizeof(Edge), byWeight); // 1) 按权重升序
    dsuInit();
    int total = 0, picked = 0;
    for (int i = 0; i < m && picked < V - 1; i++) {
        int u = edges[i].u, v = edges[i].v;
        if (find(u) != find(v)) {   // 两端不在同一集合 → 加它不成环
            unite(u, v);             // 收下、合并
            total += edges[i].w; picked++;
        }                            // 否则跳过：会成环
    }
    return total;                    // 选满 V-1 条边后即完成
}

为什么"不成环就收"是对的：每次都拿当前最便宜、又能连起两块还没连通区域的边，是一种贪心。可以证明这样选出的总权重一定最小。判环用并查集：find 看两端的"代表"是否相同，相同就说明已经连通了。
（上面的 Edge 是 {int u, v, w;} 结构体、byWeight 是给 qsort 用的"按权重升序"比较函数，例题脚手架已给好——注意合并函数不能取名 union，那是 C 关键字。）

Kruskal 演示 · 逐条加边

加权图（绿=已选入MST，橙=正在考虑，红虚=会成环被弃）

边（已按权重排序，从小到大处理）

代码

提示

点 ▶ 演示 Kruskal：边按权重从小到大处理，不成环就收（绿），成环就弃（红虚）。看总权重怎么累加到 16。

0

已选边数 (目标 V−1=4)

0

MST 总权重

3 核心要点 · 4 句人话吃透 MST

每张卡片先一句大白话。重点：MST 的三条性质、两种算法、贪心为什么对。

① MST 的三个铁律

一句话：连上所有顶点、不留环、总权重最小。三者缺一不可。

连通：每个顶点都要被连上。无环（树）：N 个顶点的树恰好 N−1 条边，多一条就成环、白增重量。最小：在所有这样的"生成树"里，权重和最小的那棵。

② 两种经典算法

一句话：Kruskal 从"边"入手（排序+并查集）；Prim 从"点"入手（从一个点长出去）。结果都是同一棵 MST。

Kruskal：所有边按权排序，逐条加不成环的（适合稀疏图）。Prim：从某顶点开始，每次加一条"连接树与外界的最便宜的边"（适合稠密图）。

③ 贪心为什么对 / 跳过成环边

一句话：每次拿"能连起两块、又最便宜"的边一定不亏；若一条边两端已连通，加它只会造环、平白增重。

这就是 Kruskal 里 find(u)==find(v) 时跳过的原因：两端已在同一棵子树里，这条边是多余的环边。

find(u)!=find(v) → 收（连起两块） find(u)==find(v) → 弃（会成环）

④ 注意：MST ≠ 最短路

一句话：MST 求的是"连通所有点的总造价最小"，不是"两点间最短路"，别和 Dijkstra 混。

MST 里两点之间的路径不一定是它们的最短路。MST 关心整体最省，最短路关心特定两点。两个不同问题、不同算法。

4 错误实验室 · 点一下亲眼看 bug

下面 4 个是写 MST 最常翻车的坑——忘判环、没排序、贪最大、把 MST 当最短路。点击卡片看运行效果。

① 忘了判环（并查集）

来者不拒地加边 → 造出环，不再是树

② 没按权重排序

按输入顺序加边 → 选不出最小总权重

③ 贪最大边

从大到小选 → 得到的是"最大"生成树

④ 拿 MST 当最短路

用 MST 上的路径当两点最短距离 → 错

// 点击上方任一卡片，查看错误推导与正确结论

$ 分析中... （等待运行...）

5 即时小测 · 5 题 + 动手例题

这 5 题正对 MST 套路：定义、Kruskal 步骤、判环、边数、本图总权重。最后到练习系统亲手算 MST 总权重。

去做例题：MST · 最小生成树总权重

去做例题

最小生成树（Prim/Kruskal）

最小生成树 MST