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

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

环境要求

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

1. Windows: 使用[Visual Studio],
2. Ubuntu: 使用 Clang 18.1.3. (Ubuntu 24.04 系统安装版本)
3. 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 算法的基本思想是从一个任意选择的起始顶点开始构建最小生成树, 逐步将距离当前生成树最近的顶点加入到生成树中, 直到所有顶点都被包含为止. 具体步骤如下:

1. 初始化:

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

2. 迭代过程:

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

3. 终止条件:

   • 当优先队列为空, 或者所有顶点都已被访问时, 算法结束. 此时, 已经找到了最小生成树.

伪代码

// 输入: 一个加权无向图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
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">