CS Wiki

21.2 Kruskal与Prim算法

41分钟阅读

相关笔记

概览

本节介绍两种经典的最小生成树（Minimum Spanning Tree, MST）算法——Kruskal算法和Prim算法。两者都基于贪心策略，利用21.1 生长最小生成树中建立的通用MST方法（GENERIC-MST），但选择了不同的安全边选取方式。Kruskal算法从边的视角出发，将所有边按权排序后依次考虑，借助不相交集合数据结构判断是否形成环；Prim算法从顶点的视角出发，从一个起点开始扩展，借助优先队列选择最小权边。

要点列表：

  • Kruskal算法的运行时间为 ====，主要开销来自排序 ，并查集操作共
  • Prim算法使用二叉堆时运行时间为 ==，使用斐波那契堆时为 ==
  • 两种算法的正确性都基于割性质（cut property）
  • Kruskal适合稀疏图，Prim适合稠密图

知识结构总览

flowchart TD
    A["21.2 Kruskal与Prim算法"] --> B["通用MST方法 (GENERIC-MST)"]
    B --> C["贪心策略: 每次选安全边"]
    C --> D["Kruskal算法"]
    C --> E["Prim算法"]

    D --> D1["核心: 按边权排序"]
    D --> D2["数据结构: 并查集"]
    D --> D3["复杂度: O(E lg V)"]
    D --> D4["适用: 稀疏图"]

    E --> E1["核心: 从顶点扩展"]
    E --> E2["数据结构: 优先队列"]
    E --> E3["二叉堆: O(E lg V)"]
    E --> E4["斐波那契堆: O(E + V lg V)"]
    E --> E5["适用: 稠密图"]

    D --> F["正确性: 割性质"]
    E --> F

核心思想

2.1 Kruskal算法

核心思路

Kruskal算法的基本策略是：将所有边按权值从小到大排序，依次考虑每条边，如果这条边连接的两个顶点当前不在同一个连通分量中（即不形成环），就将其加入MST。算法维护一个森林（forest），初始时每个顶点自成一棵树，随着边的加入，树逐渐合并，最终形成一棵完整的生成树。

这个过程就像在一个群岛中修建桥梁：先修最便宜的桥，只要两座岛之间还没有通路就修，直到所有岛都连通。

MST-KRUSKAL 伪代码

算法执行流程

  1. 将所有边按权重从小到大排序
  2. 初始化 A 为空集，每个顶点通过 MAKE-SET 自成一个独立集合
  3. 按权重从小到大遍历每条边 (u, v)
  4. 若 u 和 v 不在同一集合（FIND-SET 不同），将边加入 A，调用 UNION 合并集合
  5. 遍历完所有边后返回 A，A 即为最小生成树
flowchart TD
    A["开始：输入图 G, 权值函数 w"] --> B["A = 空集<br/>每个顶点 v 调用 MAKE-SET(v)"]
    B --> C["将所有边按权重非递减排序"]
    C --> D["取下一条最小权边 (u, v)"]
    D --> E{"FIND-SET(u)<br/>≠ FIND-SET(v)?"}
    E -- 是 --> F["A = A ∪ {(u, v)}<br/>UNION(u, v)"]
    F --> G{"还有未处理的边?"}
    E -- 否 --> G
    G -- 是 --> D
    G -- 否 --> H["返回 A<br/>A 即为最小生成树"]

MST-KRUSKAL(G, w)
1  A ← ∅
2  for each vertex v ∈ G.V
3      MAKE-SET(v)
4  sort the edges of G.E into nondecreasing order by weight w
5  for each edge (u, v) ∈ G.E, taken in nondecreasing order by weight
6      if FIND-SET(u) ≠ FIND-SET(v)
7          A ← A ∪ {(u, v)}
8          UNION(u, v)
9  return A

Kruskal算法

输入： 连通无向图 ，权值函数 输出： 最小生成树的边集

算法步骤：

  1. 初始化： ，为每个顶点 创建一个单元素集合（使用 MAKE-SET）
  2. 排序： 将 中的边按权值 非递减排序
  3. 贪心选择： 依次考虑每条边 ：
    • 若 和 属于不同集合（FIND-SET 判断），则 不会形成环
    • 将 加入 ，合并 和 所在的集合（UNION）
  4. 返回： 即为最小生成树的边集

正确性证明

运行时间分析

时间复杂度

Kruskal 算法的运行时间由以下部分组成：

  1. 初始化（第1-3行）： 对 个顶点执行 MAKE-SET，耗时
  2. 排序（第4行）： 对 条边按权值排序，耗时 （因为 ，所以 ）
  3. 主循环（第5-8行）： 共 次迭代
    • 每次 FIND-SET 操作：（使用按秩合并+路径压缩的并查集）
    • 每次 UNION 操作：
    • 总计：，其中 是反阿克曼函数（见反阿克曼函数），增长极慢，实践中可视为常数

总运行时间： ====

排序是主要瓶颈，并查集操作的总开销在渐近意义上被排序掩盖。

2.2 Prim算法

核心思路

Prim算法的基本策略是：从一个任意起始顶点开始，维护一个”已到达”顶点集合，每次选择连接已到达集合与未到达集合中权值最小的边，将该边和对应顶点加入MST。算法通过 key 数组记录每个未到达顶点连接到已到达集合的最小边权，通过优先队列高效选取最小 key 的顶点。

这个过程就像从一座城市开始修路：每次都选择从已修好路的城市到未修路的城市中造价最低的路段，逐步扩展路网直到所有城市连通。

MST-PRIM 伪代码

算法执行流程

  1. 初始化：源点 r 的 key=0，其余顶点 key=无穷大，所有顶点放入优先队列 Q
  2. while 优先队列 Q 非空
  3. 从 Q 中取出 key 最小的顶点 u
  4. 遍历 u 的每个邻接顶点 v：若 v 仍在 Q 中且 w(u,v) < key[v]，更新 key[v]=w(u,v) 和前驱 pi[v]=u
  5. Q 为空时结束，最小生成树由 A = {(v, pi[v])} 给出
flowchart TD
    A["开始：输入图 G, 权值 w, 源点 r"] --> B["初始化 key[r]=0<br/>其余 key=无穷大<br/>Q = G.V"]
    B --> C{"优先队列 Q 非空?"}
    C -- 是 --> D["u = EXTRACT-MIN(Q)<br/>取出 key 最小的顶点"]
    D --> E["遍历 u 的每个邻接顶点 v"]
    E --> F{"v 在 Q 中 且<br/>w(u,v) < key[v]?"}
    F -- 是 --> G["key[v] = w(u, v)<br/>pi[v] = u"]
    G --> H{"还有未检查的邻居?"}
    F -- 否 --> H
    H -- 是 --> E
    H -- 否 --> C
    C -- 否 --> I["结束：返回 A = {(v, pi[v])}<br/>即为最小生成树"]

MST-PRIM(G, w, r)
1  for each u ∈ G.V
2      key[u] ← ∞
3      π[u] ← NIL
4  key[r] ← 0
5  Q ← G.V
6  while Q ≠ ∅
7      u ← EXTRACT-MIN(Q)
8      for each v ∈ G.Adj[u]
9          if v ∈ Q and w(u, v) < key[v]
10             π[v] ← u
11             key[v] ← w(u, v)

Prim算法

输入： 连通无向图 ，权值函数 ，起始顶点 输出： 最小生成树，由前驱子图 给出

关键数据结构：

  • key[u]：顶点 连接到当前生成树的最小边权（初始为 ，起始顶点 的 key 为 ）
  • π[u]： 在最小生成树中的父节点
  • Q：包含所有未加入MST的顶点的最小优先队列，以 key 值为优先级

算法步骤：

  1. 初始化： 所有 key 设为 ，所有 π 设为 NIL，key[r] = 0
  2. 主循环： 当 非空时：
    • 从 中取出 key 最小的顶点 （EXTRACT-MIN）
    • 对 的每个邻居 ，若 仍在 中且 ，则更新 π[v] = u，key[v] = w(u,v)（DECREASE-KEY）

正确性证明

运行时间分析

时间复杂度——二叉堆实现

使用二叉堆作为优先队列时，Prim 算法的运行时间由以下部分组成：

  1. 初始化（第1-5行）： 构建 个元素的优先队列，耗时
  2. 主循环（第6-11行）：
    • 第7行 EXTRACT-MIN：共执行 次，每次 ，总计
    • 第9-11行的 DECREASE-KEY 操作：对每条边最多执行一次，共 次，每次 ，总计

总运行时间： ====

时间复杂度——斐波那契堆实现

使用斐波那契堆（Fibonacci heap）作为优先队列时：

  1. EXTRACT-MIN： 次，斐波那契堆的摊还代价为 每次，总计
  2. DECREASE-KEY： 次，斐波那契堆的摊还代价为 每次，总计

总运行时间： ====

当图较稠密（）时，斐波那契堆的优势明显。当图较稀疏（）时，两种实现的渐近复杂度相同，均为 。

2.3 Kruskal vs Prim 对比

选型要点

Kruskal算法适合边数较少的稀疏图，因为它的时间主要花在排序上，边越少排序越快。Prim算法适合边数较多的稠密图，尤其是使用斐波那契堆时，其复杂度仅取决于顶点数和边数的线性组合。在实际工程中，如果图的邻接信息已经以邻接矩阵形式给出，Prim的 简单实现往往是最实用的选择。

比较维度Kruskal 算法Prim 算法
核心视角全局——按边权排序，逐条考虑局部——从一个顶点向外扩展
贪心策略选权最小且不形成环的边选连接已到达集与未到达集的最小权边
关键数据结构并查集（Union-Find）优先队列（Priority Queue）
二叉堆实现
最优实现（排序瓶颈）（斐波那契堆）
邻接矩阵实现
适合场景稀疏图（）稠密图（）
并行化潜力较好（排序可并行）较差（顺序扩展）
边权相同时可能产生不同MST（取决于排序稳定性）可能产生不同MST（取决于EXTRACT-MIN的选取）

Kruskal与Prim的时间复杂度对比定理

对于连通无向图 ：

  • Kruskal算法的运行时间为 ，无论使用何种优先级队列实现，排序步骤始终是瓶颈
  • Prim算法使用二叉堆时为 ，使用斐波那契堆时为
  • 当 （即边数渐近多于顶点数）时，Prim 的斐波那契堆实现渐近快于二叉堆实现
  • 当 （稀疏图）时，Kruskal 和 Prim（无论哪种堆）的渐近复杂度相同

补充理解与拓展

MST算法的历史

最小生成树问题有着丰富的历史，三种经典算法的发现时间远早于现代计算机科学：

  1. Borůvka算法（1926年）：Otakar Borůvka 是最早系统研究 MST 问题的人。他在解决摩拉维亚电力网络最优化的实际问题时提出了这一算法。Borůvka 算法的特点是每一步中每个连通分量同时选择到其他分量的最小权边，因此天然支持并行化，在现代分布式计算中仍有应用。

  2. Jarník算法（1930年）：Vojtěch Jarník 独立发现了本质上与 Prim 相同的算法，但他的论文长期被忽视。为表彰他的贡献，该算法在中欧文献中常被称为”Jarník算法”或”Prim-Jarník算法”。

  3. Kruskal算法（1956年）：Joseph Kruskal 在贝尔实验室（Bell Labs）工作期间发表。他的论文 “On the shortest spanning subtree of a graph and the traveling salesman problem” 发表于 Proceedings of the American Mathematical Society。值得注意的是，Kruskal 当时只有23岁。

  4. Prim算法（1957年）：Robert C. Prim 在贝尔实验室独立发现了该算法。他的论文发表于 Bell System Technical Journal。Edsger Dijkstra 也在1959年独立发现了同一算法，因此该算法有时也被称为”Dijkstra-Prim算法”。

最小生成树的实际工程应用

MST 在工程和科学中有广泛的应用场景：

网络设计与基础设施：

  • 通信网络设计：在电信和计算机网络中，MST 用于确定连接所有节点的最优拓扑，最小化线缆长度和建设成本
  • 电力传输网络：确定电力线路的最优布局，确保所有区域获得电力供应的同时最小化线路总长度
  • 管道铺设：天然气、自来水等管道系统的最优铺设方案
  • 交通网络规划：道路网络规划中，用最小总长度连接所有城市

计算机科学与工程：

  • VLSI电路布线：在超大规模集成电路设计中，MST 用于优化元件间的连线布局，最小化线长和功耗
  • 聚类分析（Single-linkage clustering）：计算 MST 后删除权值最大的 条边，将图分割为 个连通分量，每个分量即为一个聚类
  • 图像分割：基于像素相似度图构建 MST，用于图像的区域分割
  • 近似算法：MST 是旅行商问题（TSP）2-近似算法的基础，也是 Steiner 树问题近似算法的组成部分
  • 网络协议：生成树协议（STP, Spanning Tree Protocol）用于防止以太网中的环路，虽然不直接使用 MST，但理论基础相同

数据科学与生物信息学：

  • 系统发育树构建：在进化生物学中，MST 用于构建物种间的进化关系树
  • 手写字体识别：使用 MST 进行特征提取

来源：Fiveable - Applications of MSTs；UT Dallas - Applications of MSTs；AlgoCademy - Prim’s Algorithm Guide

易混淆点与辨析

辨析：Kruskal vs Prim 适用场景选择

❌ 常见误区： “两种算法时间复杂度都是 ，选哪个都一样”

✅ 正确理解： 虽然使用二叉堆时两者的渐近复杂度相同，但实际性能和最优实现差异显著：

  • 稀疏图（）： Kruskal 的排序开销为 ，并查集操作接近线性，整体效率高。Prim 使用二叉堆时 DECREASE-KEY 操作次数虽少（），但 EXTRACT-MIN 仍需 ，两者相当。Prim 使用斐波那契堆时也为 ，优势不大。

  • 稠密图（）： Kruskal 的排序开销为 ，而 Prim 使用邻接矩阵的简单实现只需 ，优势明显。Prim 使用斐波那契堆时为 ，同样优于 Kruskal。

  • 图以邻接矩阵给出时： Prim 的 实现无需额外数据结构，代码简洁，通常是最佳选择。

辨析：Prim的key数组 vs Dijkstra的dist数组

❌ 常见误区： “Prim算法和Dijkstra算法几乎一样，只是把dist换成了key”

✅ 正确理解： 两种算法的伪代码结构确实高度相似，但语义有本质区别：

维度Prim 的 key[v]Dijkstra 的 dist[v]
含义 连接到当前生成树的最小边权源点到 的最短路径估计
更新条件
是否累加否，只看直接边权是，累加路径上的边权
解决的问题最小生成树单源最短路径
正确性依据割性质三角不等式 + 贪心选择

关键区别： Prim 的更新只看直接边权 ，而 Dijkstra 的更新需要加上 （从源点到 的路径总长）。这意味着 Dijkstra 要求所有边权非负，而 Prim 对边权的正负没有限制（虽然MST通常定义在无负权环的图中）。

辨析：MST-KRUSKAL中的UNION操作为什么不会出错

❌ 常见误区： “UNION操作可能会把不该合并的分量合并，导致结果不是MST”

✅ 正确理解： UNION 操作的正确性由以下逻辑保证：

  1. FIND-SET 检查确保无环： 当 FIND-SET FIND-SET 时，说明 和 在不同的连通分量中。加入边 不会在这些分量内部形成环。

  2. UNION 只合并被边连接的分量： UNION 将 和 所在的集合合并，这恰好反映了加入边 后连通关系的变化。

  3. 并查集正确维护连通性： 由于每次只加入不形成环的边，并查集始终准确反映当前森林的连通分量划分。MAKE-SET、FIND-SET、UNION 三个操作共同保证了这一不变量。

辨析：斐波那契堆在Prim中的优势

❌ 常见误区： “斐波那契堆总是比二叉堆快，应该优先使用”

✅ 正确理解： 斐波那契堆的优势体现在摊还分析（amortized analysis）层面：

  • DECREASE-KEY 操作： 斐波那契堆的摊还代价为 ，而二叉堆为 。在 Prim 算法中，DECREASE-KEY 可能被调用 次，这是关键差异所在。

  • EXTRACT-MIN 操作： 斐波那契堆的摊还代价为 ，与二叉堆相同。

  • 实际开销： 斐波那契堆的常数因子较大，实现复杂。对于中小规模图或稀疏图，二叉堆的实际性能可能更好。斐波那契堆的优势在 时才在渐近意义上体现出来。

  • 工程实践： 由于斐波那契堆实现复杂且常数因子大，许多实际系统使用二叉堆或配对堆（pairing heap）作为替代。

习题精选

题号题目描述难度
21.2-1证明对图 的每棵最小生成树 ，都存在一种边的排序方式使得 Kruskal 算法返回 ⭐⭐
21.2-2给出 Prim 算法在邻接矩阵表示下的 实现⭐⭐
21.2-3对稀疏图和稠密图，Prim 的斐波那契堆实现是否渐近快于二叉堆实现？⭐⭐⭐
21.2-5若边权为 到 $V
21.2-6 若边权在 上均匀分布，Kruskal 和 Prim 哪个能更快？⭐⭐⭐⭐
21.2-8Borden 教授的分治 MST 算法是否正确？⭐⭐⭐

视频学习指南

资源主题链接说明
MIT 6.006 Lecture 12Minimum Spanning Treeshttps://www.youtube.com/watch?v=tKwno5AdXlIKruskal与Prim的完整讲解
Abdul BariKruskal’s Algorithm MSThttps://www.youtube.com/watch?v=71UQH7Pr9kU逐步动画演示Kruskal算法
Abdul BariPrim’s Algorithm MSThttps://www.youtube.com/watch?v=cplfcGZmX7I逐步动画演示Prim算法
WilliamFisetMST (Kruskal + Prim)https://www.youtube.com/watch?v=eBbK2irCLKE两种算法的对比讲解
NeetCodeMinimum Spanning Treehttps://www.youtube.com/watch?v=4ZlRH0eT-qo实战视角的MST问题

教材原文

CLRS 第4版 21.2节原文（Kruskal算法）

Kruskal’s algorithm finds a minimum spanning tree by scanning the set of edges in monotonically increasing order by weight. In this algorithm, the set is a forest. At each step, the algorithm adds to the forest an edge of least possible weight that does not form a cycle with edges already chosen. The algorithm terminates when the forest has edges, at which point it is a minimum spanning tree.

The algorithm uses the disjoint-set data structure from Chapter 19 to maintain several disjoint sets of elements. Each set contains the vertices in one tree of the current forest. The procedure FIND-SET returns a representative element from the set that contains . Thus, by testing whether FIND-SET equals FIND-SET, the algorithm can determine whether two vertices and belong to the same tree. The procedure UNION merges the two sets containing and .

CLRS 第4版 21.2节原文（Prim算法）

Like Kruskal’s algorithm, Prim’s algorithm is a special case of the generic MST algorithm. Prim’s algorithm operates much like Dijkstra’s algorithm for finding shortest paths in a graph. Prim’s algorithm has the property that the edges in the set always form a single tree. As the algorithm proceeds, the tree is always a subtree of some minimum spanning tree. The algorithm starts from an arbitrary root vertex and grows the tree until it spans all the vertices in . At each step, a light edge connecting a vertex in to a vertex in is added to the tree.

To implement Prim’s algorithm efficiently, we use a min-priority queue that holds all vertices not yet in the tree, keyed by their key values. The attribute names the parent of in the tree.

参见Wiki

概念页尚未创建

以下概念页尚待创建，创建后可在此补充双向链接：

  • 最小生成树（Minimum Spanning Tree）
  • 割性质（Cut Property）
  • 环性质（Cycle Property）
  • Borůvka算法

第21章-最小生成树 Kruskal与Prim算法

关系图谱

反向链接