普利姆算法c++

以下是普利姆算法的 C++ 实现：

#include <iostream>
#include <vector>
#include <queue>
#include <climits>

using namespace std;

const int MAXN = 1005;
vector<pair<int, int>> adj[MAXN]; // 存储图的邻接表
bool visited[MAXN]; // 标记节点是否已经被访问
int dist[MAXN]; // 存储从源节点到 i 号节点的最小距离

int prim(int s, int n) {
    for (int i = 1; i <= n; i++) {
        visited[i] = false;
        dist[i] = INT_MAX;
    }

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push(make_pair(0, s));
    dist[s] = 0;

    int ans = 0;
    while (!pq.empty()) {
        int curr = pq.top().second;
        pq.pop();

        if (visited[curr]) {
            continue;
        }

        visited[curr] = true;
        ans += dist[curr];

        for (int i = 0; i < adj[curr].size(); i++) {
            int next = adj[curr][i].first;
            int weight = adj[curr][i].second;

            if (!visited[next] && dist[next] > weight) {
                dist[next] = weight;
                pq.push(make_pair(dist[next], next));
            }
        }
    }

    return ans;
}

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

    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back(make_pair(v, w));
        adj[v].push_back(make_pair(u, w));
    }

    cout << prim(1, n) << endl;

    return 0;
}

其中，`adj` 存储图的邻接表，`visited` 数组标记节点是否已经被访问，`dist` 数组存储从源节点到 i 号节点的最小距离。`prim` 函数返回最小生成树的权值和，参数 `s` 表示源节点编号，参数 `n` 表示节点总数。在实现中，使用了优先队列来维护当前可选的边，每次从队列中选取权值最小的边，加入到最小生成树中。