Prim最小生成树的完整代码

以下是 Prim 算法的完整代码，用于生成最小生成树：

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>

using namespace std;

#define INF INT_MAX

typedef pair<int, int> pii;

// Prim算法求解最小生成树
void Prim(int n, vector<vector<pii>>& graph) {
    vector<int> dist(n + 1, INF);    // 用于记录每个节点到当前最小生成树的距离
    vector<bool> visited(n + 1, false);    // 用于记录每个节点是否已加入最小生成树
    priority_queue<pii, vector<pii>, greater<pii>> pq;    // 小根堆，用于维护当前最小生成树的边

    // 从节点1开始，将其加入最小生成树
    dist[1] = 0;
    pq.push({0, 1});

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

        if (visited[u]) {
            continue;
        }

        visited[u] = true;

        // 遍历u的邻接节点v
        for (auto& edge : graph[u]) {
            int v = edge.first;
            int w = edge.second;

            // 如果v未被加入最小生成树，且u到v的距离比当前记录的距离更小，则更新v的距离，并将(u, v)加入小根堆
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
                pq.push({w, v});
            }
        }
    }

    // 输出最小生成树的边权和
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += dist[i];
    }
    cout << "最小生成树的边权和为：" << sum << endl;
}

int main() {
    int n, m;
    cin >> n >> m;

    // 构建邻接表表示的无向图
    vector<vector<pii>> graph(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        graph[u].push_back({v, w});
        graph[v].push_back({u, w});
    }

    Prim(n, graph);

    return 0;
}

其中，`graph` 为邻接表表示的无向图，`graph[u]` 存储节点 `u` 的所有邻接节点及其对应的边权。算法从节点1开始，将其加入最小生成树，然后遍历其邻接节点，更新其邻接节点到当前最小生成树的距离，并将其加入小根堆。每次从小根堆中取出距离最小的节点并加入最小生成树，直到所有节点都被加入最小生成树。最后输出最小生成树的边权和即可。