普利姆算法c++

普利姆算法（Prim's algorithm）是一种用于生成最小生成树的算法，它的基本思想是从任意一个顶点开始，每次选择一个与当前生成树相邻的且权值最小的边，直到生成一棵包含所有顶点的树，即最小生成树。

以下是 Prim 算法的 C++ 实现：

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

const int N = 1010;
const int INF = 0x3f3f3f3f;

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

vector<Edge> G[N];  // 存储图的邻接表
int d[N];           // 存储每个点的最小距离
bool used[N];       // 记录每个点是否被访问过

int prim(int s, int n) {
    fill(d, d + n + 1, INF);        // 初始化所有点的最小距离为 INF
    fill(used, used + n + 1, false); // 初始化所有点的访问状态为未访问
    d[s] = 0;                       // 起点的最小距离为 0
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> que;
    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 += p.first;
        for (int i = 0; i < G[v].size(); i++) {
            int to = G[v][i].to;
            int cost = G[v][i].cost;
            if (d[to] > cost && !used[to]) {
                d[to] = cost;
                que.push(make_pair(d[to], to));
            }
        }
    }
    return res;
}

int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        G[u].push_back(Edge(v, w));
        G[v].push_back(Edge(u, w));
    }
    int ans = prim(1, n);
    cout << ans << endl;
    return 0;
}

这个实现基于堆优化的 Dijkstra 算法，时间复杂度为 O(ElogV)，其中 E 和 V 分别为边数和点数。