邻接表prim最小生成树代码

Prim算法是求无向图最小生成树的经典算法之一，它可以用邻接表来实现。以下是使用邻接表实现Prim算法的代码：

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

struct Edge {
    int to;     // 目标节点
    int weight; // 边权重
    Edge(int t, int w) : to(t), weight(w) {}
};

typedef vector<vector<Edge>> Graph; // 邻接表表示的图

struct Node {
    int v;  // 节点编号
    int d;  // 从起点到该点的最小距离
    bool operator<(const Node& rhs) const { return d > rhs.d; }
};

int prim(const Graph& G, int s) {
    int n = G.size();
    vector<bool> used(n, false);
    priority_queue<Node> que;
    que.push(Node{s, 0});
    int res = 0;

    while (!que.empty()) {
        Node nd = que.top(); que.pop();
        int v = nd.v;
        if (used[v]) continue;
        used[v] = true;
        res += nd.d;

        for (auto e : G[v]) {
            if (!used[e.to]) {
                que.push(Node{e.to, e.weight});
            }
        }
    }

    return res;
}

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

    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(G, 0);
    cout << ans << endl;
    return 0;
}