学习笔记 数据结构与算法

最小生成树（Kruskal/Prim）

连通图的最小代价生成树 —— 从理论到实践的全面解析

一、最小生成树概述

最小生成树（Minimum Spanning Tree, MST） 是图论中的经典问题：给定一个连通的无向带权图 G = (V, E)，找出一个包含所有顶点的无环子集 T ⊆ E，使得 T 构成一棵树（即恰好有 |V| - 1 条边），且所有边的权值之和最小。

MST 的核心性质

  • 连通性： MST 包含原图的所有顶点，且是连通图
  • 无环性： MST 是一棵树，因此恰好有 |V| - 1 条边，不含任何环
  • 最小权值： 在所有生成树中，MST 的边权总和最小
  • 不唯一性： 当图中存在权值相等的边时，MST 可能不唯一
  • 割性质： 对于任意割，权值最小的横跨边一定在某个 MST 中
  • 环性质： 对于任意环，权值最大的边一定不在任何 MST 中

MST 问题最早由 Boruvka 在 1926 年提出（最初用于规划摩拉维亚地区的电网），随后 Kruskal（1956 年）和 Prim（1957 年）各自提出了经典的贪心算法。时至今日，MST 问题仍是算法设计课程的核心内容，并在网络设计、聚类分析、图像分割等领域有着广泛应用。

形式化定义

给定连通无向带权图 G = (V, E, w)，其中 w: E → R 是边权函数。

一棵生成树 T ⊆ E 满足：

  • (V, T) 是连通且无环的（即一棵树）
  • |T| = |V| - 1

MST 的目标是： argminT Σe∈T w(e)

二、切割定理与环性质

理解 MST 的两个关键定理是所有 MST 算法的理论基础。这两个定理揭示了边的取舍规则，是 Kruskal 和 Prim 算法的正确性证明基石。

切割定理（Cut Property）

将图 G 的顶点集 V 划分为两个非空子集 S 和 V \ S，则所有跨越这个割的边中，权值最小的那条边一定属于 G 的某个最小生成树。

证明思路： 假设存在一棵 MST T 不包含该最小权横跨边 e。将 e 加入 T 后形成环，环中必有一条其他横跨边 e'（权值 ≥ w(e)），移除 e' 得到权值不增的新生成树，与 MST 定义矛盾。

环性质（Cycle Property）

对于图中的任意环，该环上权值最大的边一定不属于图的任何最小生成树。

证明思路： 假设存在一棵 MST T 包含最大权边 e。移除 e 将 T 分成两个子树，环上必有另一条边 e' 连接这两个子树（权值 < w(e)），加入 e' 得到权值更小的生成树，矛盾。

两个定理的直观理解

  • 切割定理指导"选边"：每次选择连接两个不同连通分量的最小权边，一定不会错（Kruskal 的核心）
  • 环性质指导"删边"：对于任何环，删掉权值最大的边，一定不会丢失 MST（某些反向算法的核心）
  • 两个定理互为对偶，共同奠定了 MST 贪心算法的正确性

三、Kruskal 算法

Kruskal 算法（1956 年由 Joseph Kruskal 提出）是一种基于 边贪心 策略的 MST 算法。核心思想是：将所有边按权值从小到大排序，依次考察每条边，如果该边连接的是两个不同的连通分量，就将其加入 MST；否则丢弃该边。

算法步骤

  1. 将图中所有边按权值从小到大排序
  2. 初始化一个空的 MST 集合 T = ∅
  3. 初始化 |V| 个连通分量（每个顶点自成一派）
  4. 遍历排序后的边集：对每条边 (u, v)：
    • 如果 u 和 v 属于不同连通分量，将 (u, v) 加入 T，合并两个分量
    • 否则跳过该边（加入会形成环）
  5. 当 T 中包含 |V| - 1 条边时，算法结束

并查集（Union-Find）实现

Kruskal 算法需要高效地维护连通分量信息，并支持"查询两个顶点是否属于同一分量"和"合并两个分量"两种操作。并查集（Disjoint Set Union, DSU） 正是为此而生，配合路径压缩和按秩合并优化，单次操作的时间复杂度可达 O(α(n))（α 为阿克曼函数的反函数，可视为常数）。

#include <algorithm> #include <vector> using namespace std; struct Edge { int u, v, w; // 起点、终点、权值 bool operator<(const Edge& o) const { return w < o.w; } }; // 并查集 class DSU { vector<int> parent, rank; public: DSU(int n) : parent(n), rank(n, 0) { for (int i = 0; i < n; ++i) parent[i] = i; } int find(int x) { if (parent[x] != x) parent[x] = find(parent[x]); // 路径压缩 return parent[x]; } bool unite(int a, int b) { a = find(a), b = find(b); if (a == b) return false; if (rank[a] < rank[b]) swap(a, b); // 按秩合并 parent[b] = a; if (rank[a] == rank[b]) ++rank[a]; return true; } }; int kruskal(int n, vector<Edge>& edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int mstWeight = 0, cnt = 0; for (auto& e : edges) { if (dsu.unite(e.u, e.v)) { mstWeight += e.w; if (++cnt == n - 1) break; } } return mstWeight; }

算法分析

指标 复杂度 说明
时间复杂度 O(E log E) 主要为排序开销，并查集部分接近 O(Eα(V)) ≈ O(E)
空间复杂度 O(E + V) 存储边集和并查集结构
适用图 稀疏图 当 E ≈ V 时，O(E log E) ≈ O(V log V) 非常高效

Kruskal 算法评价

  • 优点： 实现简单直观，只需要排序和并查集；适合稀疏图，特别是边数远少于 V² 的情况
  • 缺点： 需要对所有边排序，当边数非常多时（稠密图），排序开销较大
  • 误区： 很多教材说 Kruskal 复杂度是 O(E log V)，实际应为 O(E log E)。但由于 E ≤ V²，log E = O(log V)，因此两者等价

四、Prim 算法

Prim 算法（1957 年由 Robert C. Prim 提出）采用 点贪心 策略。核心思想是：从任意一个顶点开始，维护一棵不断生长的树，每一步选择连接"树内顶点"和"树外顶点"的最小权边，将对应的树外顶点加入树中，直到所有顶点都被包含。

算法步骤（堆优化版本）

  1. 选择一个起始顶点 s，初始化距离数组 dist[v] = w(s, v)（若不存在边则为无穷大）
  2. 初始化优先队列（最小堆），将 (dist[v], v) 入队
  3. 标记 s 已访问，初始化 MST 权值和 ans = 0
  4. 循环直到队列为空：
    • 取出堆顶 (d, u)，如果 u 已访问则跳过
    • 标记 u 已访问，ans += d
    • 遍历 u 的所有邻接边 (u, v, w)：如果 v 未访问且 w < dist[v]，更新 dist[v]，将 (w, v) 入队
  5. 若所有顶点均已访问，返回 ans；否则图不连通
#include <vector> #include <queue> #include <climits> using namespace std; using PII = pair<int, int>; // (权值, 顶点编号) int prim(int n, vector<vector<PII>>& graph) { vector<bool> visited(n, false); vector<int> dist(n, INT_MAX); priority_queue<PII, vector<PII>, greater<PII>> pq; dist[0] = 0; pq.push({0, 0}); int mstWeight = 0, cnt = 0; while (!pq.empty()) { auto [d, u] = pq.top(); pq.pop(); if (visited[u]) continue; visited[u] = true; mstWeight += d; if (++cnt == n) break; for (auto [v, w] : graph[u]) { if (!visited[v] && w < dist[v]) { dist[v] = w; pq.push({w, v}); } } } return mstWeight; }

算法分析

版本 时间复杂度 空间复杂度
朴素 Prim（邻接矩阵） O(V²) O(V²)
二叉堆优化 Prim O(E log V) O(V + E)
斐波那契堆优化 Prim O(E + V log V) O(V + E)

Prim 算法评价

  • 优点： 在稠密图（E ≈ V²）上优势明显，堆优化版本实现也不复杂
  • 缺点： 需要预先建图（邻接表或邻接矩阵），空间占用与图密度相关
  • 注意： 朴素 Prim 在稠密图中反而比堆优化版本更快（O(V²) vs O(V² log V)），因为堆操作的常数较大。对于完全图，朴素 Prim 是最佳选择

五、Kruskal vs Prim 对比

两种算法都是贪心算法且都能正确求出 MST，但适用场景和实现范式有所不同。以下从多个维度进行对比：

对比维度 Kruskal 算法 Prim 算法
贪心策略 边贪心：全局选择最小边 点贪心：局部扩展最小权连接
数据结构 并查集（DSU） 优先队列（堆）/ 邻接矩阵
是否依赖图连通性 不依赖起始点，可处理非连通图（输出最小生成森林） 需要起始顶点，仅适用于连通图
稀疏图（E ≈ V） 推荐 O(E log E) ≈ O(V log V) 可行 O(E log V) ≈ O(V log V)
稠密图（E ≈ V²） 较差 O(V² log V) 推荐 O(V²) 或 O(V² log V)
代码复杂度 简单（排序 + 并查集） 中等（堆优化略复杂）
空间开销 O(E + V)，需存储边集 O(V + E)，需存储邻接表
可扩展性 易于并行化（边排序可分布式处理） 难以并行化（依赖全局状态）

选型建议

  • 稀疏图（道路网、社交网络等）： 优先选择 Kruskal。并查集简洁高效，排序复杂度可以接受
  • 稠密图（完全图、点云连接等）： 优先选择 Prim（尤其是朴素 Prim，O(V²)）。Kruskal 在对 V² 条边排序时会很慢
  • 需要最小生成森林： Kruskal 天然支持（图不连通时输出森林），Prim 需要额外处理
  • 边权动态更新： Prim 更易适应增量更新（如动态 MST 问题）

六、次小生成树

次小生成树（Second MST） 是指权值严格大于最小生成树且在所有生成树中权值第二小的生成树。求次小生成树的经典方法是：先求 MST，然后尝试替换一条边。

算法思路

  1. 先用 Kruskal 或 Prim 求出 MST，同时标记 MST 中的边
  2. 预处理 maxEdge[u][v]：在 MST 中 u → v 路径上的最大边权。可通过 DFS 或树上倍增在 O(V²) 或 O(V log V) 内完成
  3. 遍历原图中所有不在 MST 中的边 (u, v, w)：
    • 将这条非 MST 边加入 MST，会形成环
    • 环上最大权边（非 MST 边除外）就是 maxEdge[u][v]
    • 用 (u, v, w) 替换 maxEdge[u][v]，得到新的生成树，权值和为 MST_weight + w - maxEdge[u][v]
    • 在所有替换方案中取最小值，若大于 MST_weight 则为次小生成树
// 次小生成树（基于 Kruskal + 树上倍增） // 伪代码框架 int secondMST(int n, vector<Edge>& edges) { // 1. Kruskal 求 MST sort(edges.begin(), edges.end()); DSU dsu(n); vector<Edge> mstEdges; vector<vector<PII>> mstGraph(n); int mstWeight = 0; for (auto& e : edges) { if (dsu.unite(e.u, e.v)) { mstWeight += e.w; mstEdges.push_back(e); mstGraph[e.u].push_back({e.v, e.w}); mstGraph[e.v].push_back({e.u, e.w}); } } // 2. 树上倍增求任意两点路径上的最大边权 // up[k][v] = v 往上走 2^k 步到达的祖先 // maxW[k][v] = v 往上走 2^k 步路径上的最大权值 // 通过 DFS 初始化 up[0][v] 和 maxW[0][v]，然后递推 // LCA 查询时 合并两段路径的最大权值 // 3. 遍历非 MST 边，寻找替换方案 int secondMST = INT_MAX; for (auto& e : edges) { if (e.inMST) continue; // 跳过 MST 中的边 int maxOnPath = queryMaxEdge(mstGraph, e.u, e.v); if (maxOnPath < e.w) // 严格大于 secondMST = min(secondMST, mstWeight - maxOnPath + e.w); } return secondMST; }

次小生成树复杂度

  • 时间复杂度： O(E log V) — 瓶颈在 LCA 预处理和查询，总查询次数为 O(E)
  • 严格次小 vs 非严格： 要求"严格大于"时，需处理 maxOnPath == e.w 的情况，此时需要路径上的次大边权（严格次小生成树）
  • 应用场景： 网络容错设计、备选方案评估等

七、MST 的应用

MST 问题虽是图论中的经典理论问题，却在工程实践中有大量直接或间接的应用：

1. 网络设计与布线

这是 MST 最经典的应用场景。例如铺设光缆、电缆、水管等，在多个节点之间建立连接，要求连接所有节点且总成本最小。实际工程中还需考虑 Steiner 点问题（允许引入新节点以降低总成本），但 MST 提供了重要的下界参考。

  • 城市间的光纤骨干网铺设
  • 芯片内部的布线优化
  • 水/电/气管网的初始规划

2. 聚类分析（Cluster Analysis）

基于 MST 的聚类算法——如 Zahn（1971）提出的 MST 聚类——利用 MST 的树结构进行聚类：将 MST 中权值最大的 k-1 条边移除，自然得到 k 个连通分量（簇）。这种方法比 K-Means 的优势在于：

  • 不需要预设聚类形状（可发现任意形状的簇）
  • 对异常点鲁棒（孤立点往往在 MST 中连接很远）
  • 结果具有确定性和可解释性

3. 图像分割（Image Segmentation）

Felzenszwalb 和 Huttenlocher（2004 年）提出的基于图的图像分割算法（Graph-Based Image Segmentation），核心思想正是依赖 MST 的性质。将像素视为顶点，像素间差异视为边权，构建 MST 并设定自适应阈值进行区域合并，可以在保持边缘精度的同时实现高效分割。

4. 旅行商问题的近似解

Metric TSP（满足三角不等式的旅行商问题）的 2-近似算法 基于 MST：

  1. 计算图的最小生成树
  2. 对 MST 做深度优先遍历（DFS），记录访问顺序
  3. 按照访问顺序输出哈密顿回路（跳过已访问节点）

该算法保证得到的回路权值不超过最优 TSP 回路的两倍，是理论计算机科学中的经典结论。

5. 其他应用

  • 电网规划： 在多个变电站之间以最低成本铺设输电线路
  • 通信网络组播： 构建 MST 作为组播树，最小化网络延迟和带宽消耗
  • 手写体识别： 基于 MST 提取笔画特征进行字形匹配
  • 金融风控： 利用 MST 构建资产相关性树，识别系统性风险传导路径
  • 自动摘要生成： 句子间构建相似度图，MST 用于提取关键句子

八、最大生成树

最大生成树（Maximum Spanning Tree, MaxST） 是最小生成树的对偶问题：在所有生成树中，边权总和最大的那棵生成树。求解最大生成树只需要对 Kruskal 算法做一个非常简单的修改。

最大生成树的求解

方法： 将 Kruskal 算法中"从小到大排序"改为"从大到小排序"，其余逻辑完全相同。

同理，Prim 算法中将"最小堆"改为"最大堆"或取权值的相反数即可。

正确性依然由切割定理保证——对于每个割，权值最大的横跨边一定属于某个最大生成树。

// 最大生成树 —— 仅排序方向不同 // Kruskal 求最小生成树： sort(edges.begin(), edges.end()); // 从小到大 // 求最大生成树： sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) { return a.w > b.w; }); // 从大到小

最大生成树的应用

  • 瓶颈优化问题： 最大化路径上的最小边权（Maximin Path），即所有路径中最小边权最大化的路径——最大生成树上的路径就是所求
  • 聚类评估： 在层次聚类中，往往结合最小和最大生成树来评估聚类的分离度和紧密度
  • 网络可靠性： 在通信网络中，最大生成树用于最大化两节点间的最小可用带宽

九、MST 的唯一性判断

前文提到，当原图中存在权值相等的边时，MST 可能不唯一。那么如何判断给定图的 MST 是否唯一？这里有几种常用的判断方法。

唯一性判定定理

图 G 的最小生成树唯一的 充要条件 是：对于任意一条不在 MST 中的边 e = (u, v, w)，MST 中 u 到 v 路径上的最大边权 严格小于 w（而非小于等于）。

等价表述： 如果将权值相等的边任意排列，Kruskal 算法执行过程中，对每条边是否加入 MST 的决策不受排序顺序的影响。

判定方法一：Kruskal 变法

执行 Kruskal 时，将权值相同的边分为一组。对每组内的边，先检查其是否连接不同连通分量（记录结果但不合并），再统一合并。如果组内有两条或以上边可以加入，则 MST 不唯一。

bool isUnique(int n, vector<Edge>& edges) { sort(edges.begin(), edges.end()); DSU dsu(n); int i = 0, m = edges.size(); while (i < m) { // 找出所有权值相同的边 int j = i; while (j < m && edges[j].w == edges[i].w) ++j; // 第一遍：只检查，不合并 int cnt = 0; for (int k = i; k < j; ++k) if (dsu.find(edges[k].u) != dsu.find(edges[k].v)) ++cnt; // 第二遍：执行合并 for (int k = i; k < j; ++k) dsu.unite(edges[k].u, edges[k].v); if (cnt > 1) return false; // 不唯一 i = j; } return true; }

判定方法二：次小生成树法

求次小生成树：如果次小生成树的权值等于 MST 的权值，则 MST 不唯一；否则唯一。此方法需要求出完整的次小生成树，复杂度较高但概念直观。

唯一性的实践意义

  • 在工程布线中，唯一性意味着设计方案不可替代——不存在其他同样低成本的备选方案
  • 在聚类分析中，不唯一性反映了数据的模糊性——两种不同的 MST 可能产生不同的聚类结果
  • 在算法竞赛中，判断 MST 唯一性是常见考点，熟练掌握 Kruskal 变法能在 O(E log E) 内解决

十、核心要点总结