DSA Mastery理论与实验教程

外观

第 7 章 · 图的遍历与应用

7.2 最小生成树

最小生成树的定义、切分定理与环性质，Prim 与 Kruskal 的实现与选型。

约 6 分钟阅读更新于 2026-08-25Fishmandraft

在带权图上，有一个经典问题把"贪心"落到实处：最小生成树（Minimum Spanning Tree，MST）用最小的边权总和连通全部顶点。它依靠"每一步做局部最优选择"的贪心方法，背后的理论支撑是切分定理与环性质。理解"为什么贪心在这里是对的"，比单纯硬背代码更重要。

学习目标 ​

  • 说出生成树与最小生成树的定义，理解 n 个顶点的树恰有 n−1 条边；
  • 陈述并论证切分定理与环性质；
  • 实现 Prim 与 Kruskal算法，分析各自复杂度；
  • 说明两种算法的适用与不适用场景，并据此选型；

最小生成树的概念 ​

生成树（Spanning Tree）：设 G=(V,E) 是连通无向图，G 的一棵生成树是包含全部 n=|V| 个顶点、不含环且连通的子图。生成树恰好有 n−1 条边——少一条就不连通，多一条必成环。

最小生成树（MST）：在所有生成树中，边权总和最小的一棵。这里的"最小"指边权和，而不是边数或最长边，请注意，这里的边权有可能是负数，因此最小生成树的边权和可能是负数。

理解生成树，先记住三条由"树"的定义直接推出的性质：

  • n 个顶点的树恰有 n−1 条边；
  • 树中任意两顶点之间有且仅有一条简单路径；
  • 给树加任意一条边，会形成唯一一个环；删去树上任意一条边，图不再连通。

最小生成树可能不唯一

当图中存在多条权值相等的边时，MST 通常不止一棵；但最小边权和是唯一确定的。反过来，若所有边权两两不同，则 MST 唯一（见下文定理）。算法返回哪一棵，取决于选边的具体顺序，这不影响"和最小"这个结论。

生成最小生成树：贪心框架 ​

生成 MST 的通用做法是一个贪心框架：维护一个边集 A，始终保持 A 是"某棵 MST 的子集"；每轮往 A 里加一条安全边，直到 A 有 n−1 条边。所谓"安全边"，就是"加进去之后 A 仍然是某棵 MST 的子树"的边。

Prim 与 Kruskal 的区别，只在于"如何找安全边"：Prim 维护一棵连通的树，每次选跨越"树内/树外"的最小边；Kruskal 维护一片森林，每次选不形成环的最小边。它们共享同一个正确性来源——下面两条定理。

两条核心定理 ​

切分定理（Cut Property） ​

把顶点集 V 分成两个非空且不交的部分 S 与 V−S，称 (S,V−S) 是一个切分；端点分别落在两侧的边称为跨越切分的边。

切分定理：对任意切分 (S,V−S)，若 e=(u,v) 是跨越该切分的最小权边，则 e 一定属于某棵 MST。

证明（交换法）：设 T 是任意一棵 MST。若 e∈T 已成立；否则，在 T 中连接 u 与 v 的唯一路径上，必存在一条也跨越 (S,V−S) 的边 e′（因为路径从 S 出发、终点在 V−S）。由于 e 是跨越切分的最小权边，w(e)≤w(e′)。把 T 中的 e′ 换成 e，得到新的生成树 T′，其边权和 w(T′)≤w(T)；又 T 已是最小，故 w(T′)=w(T)，T′ 也是 MST，且含 e。证毕。

切分定理给出了一种"安全边"的识别方法：跨越某个切分的最小权边，一定是安全边。Prim 每一步取的正是"当前树 S 与树外 V−S"这个切分的最小边。简单地讲，Prim就是每次选取与当前MST相连的最小边，并将其添加至当前MST中。

环性质（Cycle Property） ​

环性质：无向图中，任意一个环上权值最大的边（若最大边唯一）不属于任何 MST。

证明（反证）：设 e 是环 C 上唯一的最大权边，且 e 属于某棵 MST T。从 T 删去 e 会把 T 分成两个连通分量；环 C 上必存在另一条边 e′ 连接这两个分量（否则 C∖{e} 无法让删边后的两部分重新连通）。把 e 换成 e′ 得到新生成树，边权减少（w(e′)<w(e)），与 T 最小矛盾。证毕。

环性质是 Kruskal 避免成环的理论依据：一旦某条边会让当前森林成环，它就是这个环上的最大权边，不该选。切分定理与环性质互为对偶——切分定理说"某些边必在 MST 中"，环性质说"某些边必不在 MST 中"。

由定理得到的两个推论 ​

  • 唯一性：若所有边权两两不同，则 MST 唯一。因为此时每个切分的最小边、每个环的最大边都唯一，选边过程被完全确定。
  • 贪心安全：只要始终选"跨越某切分的最小边"且"不选环上最大边"，最终得到的必然是 MST。

Prim 算法 ​

Prim 从任意一个起点出发，把已选顶点看作集合 S，每轮在"一端在 S、一端在 V−S"的边里挑最小权的一条，把新顶点并入 S。这正是切分定理的直接应用：每次选的边都是跨越切分 (S,V−S) 的最小边。

朴素实现维护一个距离数组 dist[v]（v 到当前树的最小边权），每轮线性扫描找最小 dist，共 n 轮，每轮 O(n)：

T(n)=O(n2).
cpp
// 邻接矩阵 g[u][v] = 边权；INF 表示无边；n 为顶点数（0-based）
int prim(const std::vector<std::vector<int>>& g, int n) {
    std::vector<int> dist(n, INF);   // dist[v]：v 到当前树的最小边权
    std::vector<bool> inTree(n, false);
    int total = 0;
    dist[0] = 0;                     // 从顶点 0 开始
    for (int i = 0; i < n; ++i) {
        int u = -1;
        for (int v = 0; v < n; ++v)  // 选 dist 最小且不在树内的顶点
            if (!inTree[v] && (u == -1 || dist[v] < dist[u])) u = v;
        if (u == -1 || dist[u] == INF) return -1; // 图不连通
        inTree[u] = true;
        total += dist[u];
        for (int v = 0; v < n; ++v)  // 用 u 松弛邻居
            if (!inTree[v] && g[u][v] < dist[v]) dist[v] = g[u][v];
    }
    return total;
}
prim.cpp

若用邻接表 + 二叉堆维护"当前到树的最小边权"，每轮取堆顶 O(log⁡n)、松弛总次数 O(m)，复杂度降为：

T(n,m)=O((n+m)log⁡n).

稠密图别急着上堆

堆优化 Prim 在稀疏图（m 接近 n）上才划算；稠密图（m 接近 n2）时堆的 O(mlog⁡n) 反而比朴素版 O(n2) 更差。判断标准是看 m 与 n 的相对大小，而不是"堆一定更快"。

Kruskal 算法 ​

Kruskal 把所有边按权值升序排序，从最小边开始逐条考虑：若这条边的两个端点当前不在同一连通分量（加入后不成环），就选中它并合并两个分量。连通性用并查集维护。

正确性分两步：当候选边跨越两个连通分量时，它正是跨越"该分量与其他顶点"这个切分的最小权边（切分定理，安全）；当候选边两端同属一个分量时，它会形成环，且是环上最大边（环性质，应跳过）。

排序占主导，总复杂度：

T(m)=O(mlog⁡m).
cpp
struct Edge { int u, v, w; bool operator<(const Edge& o) const { return w < o.w; } };

struct DSU {
    std::vector<int> p;
    DSU(int n) : p(n, -1) {}
    int find(int x) { return p[x] < 0 ? x : p[x] = find(p[x]); }
    void unite(int a, int b) { a = find(a); b = find(b); if (a != b) p[a] = b; }
};

int kruskal(std::vector<Edge> edges, int n) {
    std::sort(edges.begin(), edges.end());   // 按权值升序
    DSU dsu(n);
    int total = 0, cnt = 0;
    for (auto [u, v, w] : edges) {
        if (dsu.find(u) != dsu.find(v)) {    // 不成环才加入
            dsu.unite(u, v);
            total += w;
            if (++cnt == n - 1) break;       // 已选满 n-1 条边
        }
    }
    return cnt == n - 1 ? total : -1;        // 不足 n-1 条说明图不连通
}
kruskal.cpp

算法的适用范围与选择 ​

Prim 与 Kruskal 都能正确求出 MST，选谁取决于图的稠密程度和存储表示：

场景推荐算法复杂度说明
稠密图（m≈n2）Prim 朴素版O(n2)邻接矩阵扫描，常数小
稀疏图（m≈n）KruskalO(mlog⁡m)排序 + 并查集，实现简单
稀疏图，边已按权排序KruskalO(mα(n))省去排序，几乎线性
稀疏图，需堆优化Prim + 堆O((n+m)log⁡n)邻接表 + 优先队列

各自的"不适用"部分：

  • Prim 朴素版在稀疏图上浪费：O(n2) 中大量时间花在扫描无边连接的顶点上。
  • Prim 堆优化在稠密图上退化：松弛次数 m 接近 n2，堆操作反而拖慢。
  • Kruskal 需要先把边排序；若图是动态的、边频繁变化，反复排序不划算。
  • 三者都要求图连通：图不连通时，Kruskal 得到的是最小生成森林，Prim 则只能覆盖起点所在连通分量（即只能得到起点的MST）。

选型口诀

先看稠密还是稀疏，再看有无排序/堆的现成条件。稠密图选 Prim（矩阵），稀疏图选 Kruskal，是竞赛与工程里最常用的两条默认规则；需要精确到常数时再考虑堆优化 Prim。

参考资料 ​

  • 《洛谷深入浅出程序设计竞赛》图论部分（最小生成树）
  • 王道《数据结构》考研复习指导：图的应用（最小生成树）
  • 严蔚敏《数据结构》（C 语言版）：图的生成树

彩蛋 ​

  • 希望大家能在看完这章后能有所体悟，如果真的有所体悟，可能就会有下图表情（狗头）
  • 哦耶~

春风得意