算法设计-普里姆算法（C++）

一、适用场景

用于求解无向连通图的 最小生成树（Minimum Spanning Tree, MST）。最小生成树是一个包含图中所有节点的树，且树中所有边的权重之和最小。

二、详细代码

//
// Created by 24978 on 2024/11/26.
//


#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;

struct Edge {
    int to;
    int weight;
};

struct Compare {
    bool operator()(const pair<int, int>& a, const pair<int, int>& b) {
        return a.second > b.second; // 小顶堆
    }
};

void prim(vector<vector<Edge>>& graph, int n) {
    vector<bool> inMST(n, false); // 是否在 MST 中
    vector<int> key(n, INT_MAX);  // 记录每个节点到 MST 的最小边权重
    vector<int> parent(n, -1);     // 记录每个节点的父节点

    // 优先队列，存储 (节点, 权重) 对
    priority_queue<pair<int, int>, vector<pair<int, int>>, Compare> pq;

    // 从节点 0 开始
    key[0] = 0;
    pq.push({0, 0});

    while (!pq.empty()) {
        int u = pq.top().first;
        pq.pop();

        if (inMST[u]) continue; // 已经在 MST 中，跳过
        inMST[u] = true;

        for (const Edge& edge : graph[u]) {
            int v = edge.to;
            int weight = edge.weight;

            if (!inMST[v] && weight < key[v]) {
                parent[v] = u;
                key[v] = weight;
                pq.push({v, weight});
            }
        }
    }

    // 输出最小生成树的边
    cout << "Minimum Spanning Tree Edges:" << endl;
    for (int i = 1; i < n; ++i) {
        cout << parent[i] << " - " << i << " : " << key[i] << endl;
    }
}

int main() {
    int n = 5; // 节点数
    vector<vector<Edge>> graph(n);

    // 添加边
    graph[0].push_back({1, 2});
    graph[1].push_back({0, 2});
    graph[0].push_back({3, 6});
    graph[3].push_back({0, 6});
    graph[1].push_back({2, 3});
    graph[2].push_back({1, 3});
    graph[1].push_back({4, 5});
    graph[4].push_back({1, 5});
    graph[2].push_back({4, 7});
    graph[4].push_back({2, 7});
    graph[3].push_back({4, 9});
    graph[4].push_back({3, 9});

    prim(graph, n);

    return 0;
}

三、结构体

 Edge 结构体

• Edge 结构体表示图中的一条边。

• to：边的目标节点。

• weight：边的权重。

Compare 结构体

• Compare 是一个用于优先队列的比较器。

• 它定义了如何比较两个 pair<int, int> 对象，确保权重较小的节点在优先队列中排在前面。

• 这里使用小顶堆（最小堆），以便每次从队列中取出权重最小的边。

四、主要函数

 prim 函数

参数

• graph：图的邻接表表示，graph[i] 存储与节点 i 相连的所有边。

• n：图的节点数。

变量

• inMST：布尔数组，记录每个节点是否已经在最小生成树中。

• key：数组，记录每个节点到最小生成树的最小边权重。

• parent：数组，记录每个节点的父节点，用于构建最小生成树。

• pq：优先队列，存储 (节点, 权重) 对，用于选择权重最小的边。

算法步骤

1. 初始化：

   • 将 key[0] 设为 0，表示从节点 0 开始。

   • 将 (0, 0) 推入优先队列。

2. 主循环：

   • 从优先队列中取出权重最小的节点 u。

   • 如果 u 已经在最小生成树中，跳过。

   • 否则，将 u 标记为已加入最小生成树。

   • 遍历 u 的所有邻接节点 v：

     • 如果 v 不在最小生成树中，且边 (u, v) 的权重小于 key[v]，则更新 key[v] 和 parent[v]，并将 (v, weight) 推入优先队列。

3. 输出结果：

   • 遍历 parent 数组，输出最小生成树的边及其权重。