图的最小生成树算法:Prim算法和Kruskal算法(C++)

上一节我们学习了最短路径算法, 这一节来学习最小生成树.

最小生成树(Minimum Spanning Tree, MST)算法是图论中的一种重要算法, 主要用于在加权无向图中找到一棵生成树, 使得这棵树包含图中的所有顶点, 并且所有边的权重之和最小. 这样的树被称为最小生成树. 最小生成树广泛应用于网络设计, 电路布线等领域. 主要有两种算法 Prim 算法和 Kruskal 算法.

环境要求

本文所用样例在Windows 11以及Ubuntu 24.04上面编译通过.

Windows: 使用[Visual Studio], Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本) GCC 无法编译直接本项目代码, 因为本文代码使用了 C++20 Module, 而 GCC 对此支持不完整.

关于 Module 的更多信息, 请参考我之前的博客: CMake 构建 C++20 Module 实例(使用 MSVC)

本项目工程目录: 图论代码

Prim 算法

Prim 算法是一种用于寻找加权无向图的最小生成树(Minimum Spanning Tree, MST)的经典贪心算法. 它由捷克数学家 Vojtěch Jarník 在 1930 年提出, 后来又被计算机科学家 Robert C. Prim 独立发现, 并因此得名. Prim 算法特别适用于稠密图, 即边的数量接近顶点数平方的情况.

算法步骤

Prim 算法的基本思想是从一个任意选择的起始顶点开始构建最小生成树, 逐步将距离当前生成树最近的顶点加入到生成树中, 直到所有顶点都被包含为止. 具体步骤如下:

初始化:

选择任意一个顶点作为起始点, 将其标记为已访问. 初始化一个优先队列(或最小堆), 用来存储尚未访问的顶点及其与当前生成树的最短距离. 初始时, 除了起始顶点外, 其他所有顶点的距离设为无穷大(表示还未连接).

迭代过程:

从优先队列中取出距离当前生成树最近的顶点 u u u, 并将其标记为已访问. 对于顶点 u u u 的所有邻接顶点 v v v, 如果 v v v 尚未被访问, 并且通过 u u u 到达 v v v 的距离比之前记录的距离更短, 则更新 v v v 的距离值, 并将( v v v, 距离)对插入或更新到优先队列中.

终止条件:

当优先队列为空, 或者所有顶点都已被访问时, 算法结束. 此时, 已经找到了最小生成树. 伪代码 // 输入: 一个加权无向图G = (V, E), 其中V是顶点集合, E是边集合 // 输出: 最小生成树MST的边集 Prim(G, start_vertex): // 初始化 MST = [] // 存储最小生成树的边 priority_queue = new MinHeap() // 优先队列(最小堆), 存储(权重, 顶点)对 visited = new Set() // 已访问顶点集合 add start_vertex to visited // 将起始顶点的所有邻接边加入优先队列 for each neighbor in G.adjacent(start_vertex): if neighbor not in visited: priority_queue.insert((neighbor, weight(start_vertex, neighbor), start_vertex)) // 主循环 while not priority_queue.isEmpty(): // 取出优先队列中权重最小的边(u, v) (u, weight_uv, previous_u) = priority_queue.extractMin() if u in visited: continue // 如果顶点u已经被访问过, 则跳过 // 将顶点u标记为已访问, 并将边(previous_u, u)加入MST add u to visited add (previous_u, u, weight_uv) to MST // 对于顶点u的所有邻接顶点v for each (v, weight_u_v) in G.adjacent(u): if v not in visited: // 将(v, 权重)对插入或更新到优先队列中 priority_queue.insertOrDecreaseKey((v, weight_u_v, u)) return MST 样例

考虑下面这个图, 求它的最小生成树.

初始化: 假设我们从G开始访问, 此时标记G为已访问, 并将与G相邻的点加入到优先队列中. 设置其他点的距离为无穷大.

迭代过程:

从优先队列中取出(G, C), 将C标记为已访问, 将G-C这条边加入到结果集中. 访问C的邻接点[A, B, D], 更新他们的距离, 由于新的距离更小, 所以将[A, B, D]加入优先队列中.

从优先队列中取出(C, A). 将A标记为已访问, 将C-A这条边加入到结果集中. 访问A的邻接点[B, C, D, H], 其中C已经访问过, 跳过. 将其他的边加入优先队列中.

从优先队列中取出(A, B). 将B标记为已访问, 将A-B这条边加入到结果集中. 访问B的邻接点[A, C, D, E], A, C均已访问, 跳过; 将其他的边加入优先队列中.

从优先队列中取出(B, E). 将E标记为已访问, 将B-E这条边加入到结果集中. 访问E的邻接点[B, D, F, H], B以访问,跳过. 将其他的边加入优先队列中.

从优先队列中取出(B, D). 将D标记为已访问, 将B-D这条边加入到结果集中. 访问D的邻接点[A, B, C, E, F], 其中[A, B, C, E]已访问, 跳过. 将D,F加入优先队列.

跳过(C, B), (A,D) , (C,D)

从优先队列中取出(D, F). 将F标记为已访问, 将D-F这条边加入到结果集中. 访问F的邻接点[D, E], 均已访问过, 跳过.

从优先队列中取出(G, H). 将H标记为已访问, 将G-H这条边加入到结果集中. 访问H的邻接点[A, E, G], 均已访问, 跳过.

其他边的顶点都已经访问过, 均被跳过, 算法结束. 得到的最小生成树如下:

实现细节 typedef std::pair<unsigned, int> EdgeWithWeight; class Prim { public: