用Prim法求连通图的最小生成树（邻接表）

Prim算法是一种贪心算法，从一个起点开始，每次选取与当前生成树相邻的最小边加入生成树中，直到所有节点都被包含在生成树中。邻接表适合用堆来实现优化，时间复杂度为O(ElogV)，其中E为边数，V为节点数。

以下是用Prim法求连通图最小生成树的代码实现：

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

using namespace std;

const int INF = 0x3f3f3f3f; // 定义无穷大

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

vector<Edge> adj[100]; // 邻接表存储图
bool visited[100]; // 标记节点是否已经加入生成树

int Prim(int start) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    int mst = 0; // 最小生成树的权值
    pq.push(make_pair(0, start)); // 将起点加入堆中
    while (!pq.empty()) {
        int u = pq.top().second, w = pq.top().first;
        pq.pop();
        if (visited[u]) continue; // 如果节点已经被访问过，跳过
        visited[u] = true; // 标记节点为已访问
        mst += w; // 更新最小生成树的权值

        // 遍历u的所有邻居节点
        for (auto edge : adj[u]) {
            int v = edge.to, w = edge.w;
            if (!visited[v]) {
                pq.push(make_pair(w, v)); // 将邻居节点加入堆中
            }
        }
    }

    return mst;
}

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));
    }

    int start = 1; // 选择一个起点开始Prim算法
    int mst = Prim(start);
    cout << "最小生成树权值为：" << mst << endl;

    return 0;
}

在上面代码中，我们使用堆来优化Prim算法，使用visited数组来标记节点是否已经被访问过，使用邻接表存储图。算法的时间复杂度为O(ElogV)，其中E为边数，V为节点数。