prim算法c++实现

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

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

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

struct Edge {
    int to; // 边的终点
    int w; // 边的权值
    Edge(int _to, int _w): to(_to), w(_w) {}
};

vector<Edge> adj[MAXN]; // 邻接表存图
int dist[MAXN]; // 记录每个点到当前生成树的距离
bool vis[MAXN]; // 标记每个点是否已经加入生成树

int Prim(int s) {
    memset(dist, INF, sizeof(dist)); // 初始化距离为无穷大
    memset(vis, false, sizeof(vis)); // 初始化所有点都未加入生成树

    priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;
    // 小根堆，存储 (点到生成树的最短距离, 点的编号) 的二元组

    dist[s] = 0;
    pq.push(make_pair(0, s)); // 将起点加入堆中

    int ans = 0; // 记录生成树的总权值

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

        if (vis[u]) continue; // 如果该点已经加入生成树，则跳过

        vis[u] = true; // 将该点加入生成树

        ans += dist[u]; // 更新生成树的总权值

        for (unsigned int i = 0; i < adj[u].size(); ++i) {
            int v = adj[u][i].to;
            int w = adj[u][i].w;

            if (!vis[v] && w < dist[v]) {
                dist[v] = w;
                pq.push(make_pair(dist[v], v)); // 将 v 加入堆中
            }
        }
    }

    return ans;
}

int main() {
    int n, m;
    cin >> n >> m; // 输入点数和边数

    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w; // 输入一条边的起点、终点和权值
        adj[u].push_back(Edge(v, w));
        adj[v].push_back(Edge(u, w)); // 无向图
    }

    cout << Prim(1) << endl; // 从第一个点开始生成最小生成树

    return 0;
}

该算法的时间复杂度为O(mlogn)，其中n为点数，m为边数。