Prim 最小生成树算法

Prim 算法定义

Prim (普里姆) 算法是一种常见的**贪心算法**，用于在**带权无向连通图**中查找**最小生成树 (Minimum Spanning Tree, MST)**。

该算法从图中的任意一个顶点开始，逐步选择连接到当前已构建树的、权重最小的边，不断扩展这棵树，直到它包含了图中的所有顶点。

关键点： Prim 算法始终维护一个连通的树结构，每次选择一条权重最小的**跨边**（一个端点在树内，一个端点在树外）来扩展这棵树。

应用场景

Prim 算法及其核心思想（构建最小成本连接）在许多现实问题中非常有用：

网络设计： 设计成本最低的通信网络（如铺设光缆）。
电路布线： 在电路板上连接所有引脚，使用最少的导线长度。
道路规划： 规划道路网以最低成本连接所有城镇。
聚类分析： 在某些聚类算法中用于构建簇连接。
管道系统： 设计最优的供水或供暖管道网络。

关键点： 任何需要以最小总代价连接所有“点”的问题，都可能考虑使用最小生成树算法（如 Prim 或 Kruskal）。

算法思路概览

Prim 算法的执行过程可以概括为以下步骤：

初始化： 选择一个任意顶点作为起始点，将其加入“已访问”集合（构成初始的树）。
寻找最小跨边： 检查所有连接“已访问”顶点与“未访问”顶点的边（称为“跨边”），找到其中权重最小的那条边。
加入树： 将这条最小权重的跨边及其连接的“未访问”顶点加入到当前的生成树中。将新加入的顶点标记为“已访问”。
重复： 重复步骤 2 和 3，每次都选择连接当前树与树外顶点的最小权重边，直到所有顶点都被包含在树中。

关键点： 算法的核心在于维护一个“候选边”集合（通常用优先队列实现），并总是从中选取权重最小的有效跨边。

Prim 算法可视化演示

控制面板

选择起始顶点：

动画速度：中

候选边列表

MST 边集

算法步骤提示

请点击“生成示例图”开始。

Prim 算法 C++ 实现 (优先队列优化)

// C++ 实现 Prim 算法查找最小生成树 (使用优先队列优化)
#include <bits/stdc++.h>
using namespace std;

// 定义无穷大常量
const int INF = INT_MAX
// 定义图的边结构
struct Edge {
    int to;     // 边的终点
    int weight; // 边的权重

    // 重载大于运算符，用于优先队列（最小堆）
    // 注意：优先队列默认是最大堆，所以要反向定义比较逻辑
    bool operator>(const Edge& other) const {
        return weight > other.weight;
    }
};

// 定义用于存储MST结果的边
struct MSTEdge {
    int u, v, weight;
};

// Prim 算法函数
vector primMST(int startNode, int V, const map>& adjList) {
    // 存储到各个顶点的最小权重，初始化为无穷大
    vector minWeight(V, INF);
    // 存储生成树中每个顶点的前驱顶点，初始化为-1
    vector parent(V, -1);
    // 标记顶点是否已经加入MST，初始化为 false
    vector inMST(V, false);
    // 存储最终MST的边
    vector resultMST;
    // 记录MST的总权重
    long long totalWeight = 0;

    // 使用优先队列存储候选边 {权重, 目标顶点}
    // C++ 的 priority_queue 默认是最大堆，我们需要最小堆
    // 存储 Edge 结构，并使用自定义的 > 运算符
    priority_queue, greater> pq;

    // 算法从起始顶点开始
    minWeight[startNode] = 0;
    pq.push({startNode, 0}); // {目标顶点, 权重} - 初始权重为0

    while (!pq.empty()) {
        // 从优先队列中取出当前权重最小的边连接的顶点
        Edge current = pq.top();
        pq.pop();
        int u = current.to;
        int w = current.weight; // 这是到达 u 的最小权重

        // 如果顶点 u 已经被访问过（或者这条边是旧的、权重更大的边），则跳过
        if (inMST[u] || w > minWeight[u]) {
            continue;
        }

        // 将顶点 u 加入 MST
        inMST[u] = true;
        totalWeight += w; // 累加权重

        // 如果 u 不是起始节点 (parent[u] != -1)，则将边 (parent[u], u) 加入结果集
        if (parent[u] != -1) {
            resultMST.push_back({parent[u], u, w});
        }

        // 遍历与 u 相邻的所有顶点 v
        if (adjList.count(u)) { // 检查 u 是否有邻接边
            for (const auto& edge : adjList.at(u)) {
                int v = edge.to;
                int edgeWeight = edge.weight;

                // 如果顶点 v 不在 MST 中，并且通过 u 到达 v 的权重更小
                if (!inMST[v] && edgeWeight < minWeight[v]) {
                    // 更新到达 v 的最小权重
                    minWeight[v] = edgeWeight;
                    // 更新 v 的父节点为 u
                    parent[v] = u;
                    // 将新的候选边 {v, minWeight[v]} 加入优先队列
                    pq.push({v, minWeight[v]});
                }
            }
        }
    }

    // 检查是否所有顶点都已连接 (适用于图不连通的情况)
    // if (resultMST.size() < V - 1) {
    //     cout << "图不连通，无法生成覆盖所有顶点的MST" << endl;
    // }

    cout << "Prim 算法完成。最小生成树总权重: " << totalWeight << endl;
    return resultMST;
}

// --- 示例用法 ---
// int main() {
//     int V = 6; // 顶点数 (0 到 5)
//     map> adjList; // 邻接列表

//     // 添加边 (无向图，需要双向添加)
//     auto addEdge = [&](int u, int v, int w) {
//         adjList[u].push_back({v, w});
//         adjList[v].push_back({u, w});
//     };

//     addEdge(0, 1, 4); addEdge(0, 2, 3);
//     addEdge(1, 2, 1); addEdge(1, 3, 2);
//     addEdge(2, 3, 4); addEdge(2, 4, 3);
//     addEdge(3, 4, 2); addEdge(3, 5, 5);
//     addEdge(4, 5, 6);

//     int startNode = 0; // 选择起始节点
//     vector mst = primMST(startNode, V, adjList);

//     cout << "\n最小生成树的边:" << endl;
//     for (const auto& edge : mst) {
//         cout << edge.u << " -- " << edge.v << " (权重: " << edge.weight << ")" << endl;
//     }

//     return 0;
// }