最小生成树普里姆算法代码

Prim算法是一种常用的最小生成树算法，它的思想是从一个源节点开始，每次选择一个与当前树相邻的最小权值边所连接的节点，将其加入到当前树中，直到所有的节点都被加入为止。以下是Prim算法的伪代码：

1. 选取一个起始节点 s ，将它加入到最小生成树中，并将其权值设为0
2. 重复执行以下步骤，直到所有节点都被加入到最小生成树中：
a. 从当前最小生成树中所有节点所连接的边中选择一条权值最小的边 (u,v)，并且 v 不在最小生成树中。
b. 将 v 加入到最小生成树中，并将(u,v)的权值设为 v 到最小生成树中某个节点的距离。

以下是Prim算法的代码实现（C++版本）：

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

const int MAXN = 1005; // 最大点数
const int INF = 0x3f3f3f3f; // 无穷大

struct Edge {
    int to, w;
    Edge(int to, int w) : to(to), w(w) {}
};

vector<Edge> G[MAXN]; // 邻接表存储图
int d[MAXN]; // d[i]表示i到最小生成树的距离
bool used[MAXN]; // used[i]表示i是否已经被加入到最小生成树中

int Prim(int s) {
    memset(d, INF, sizeof(d)); // 初始化距离
    memset(used, false, sizeof(used)); // 初始化状态
    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > que; // 建立小根堆，维护距离最小的点
    d[s] = 0; // 起始点到自己的距离为0
    que.push(make_pair(0, s)); // 将起始点加入堆中
    int res = 0; // 最小生成树的权值
    while (!que.empty()) {
        pair<int, int> p = que.top();
        que.pop();
        int v = p.second;
        if (used[v]) continue; // 如果这个点已经被加入到最小生成树中，则跳过
        used[v] = true; // 将这个点加入到最小生成树中
        res += d[v]; // 更新最小生成树的权值
        for (int i = 0; i < G[v].size(); i++) { // 遍历当前点所连接的边
            int u = G[v][i].to;
            if (d[u] > G[v][i].w && !used[u]) { // 如果 u 不在最小生成树中且连接 v 和 u 的边更短
                d[u] = G[v][i].w; // 更新 u 到最小生成树的距离
                que.push(make_pair(d[u], u)); // 将 u 加入堆中，更新下一次遍历的点
            }
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m; // 输入点数和边数
    for (int i = 0; i < m; i++) {
        int x, y, w;
        cin >> x >> y >> w; // 输入边的起点、终点和权值
        G[x].push_back(Edge(y, w)); // 添加一条从 x 到 y 权值为 w 的边
        G[y].push_back(Edge(x, w)); // 添加一条从 y 到 x 权值为 w 的边（如果是无向图）
    }
    cout << Prim(1) << endl; // 从节点1开始运行Prim算法，输出最小生成树的权值
    return 0;
}