图与网络分析最小生成树问题 C++代码

下面是使用Prim算法求解最小生成树的C++代码：

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

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

// 边的结构体
struct Edge {
    int to;  // 连接的顶点
    int weight;  // 权重
    Edge(int _to, int _weight): to(_to), weight(_weight) {}
};

vector<Edge> G[MAXN];  // 图的邻接表表示
int dist[MAXN];  // 存储每个顶点到已选中顶点集合的最短距离
bool visited[MAXN];  // 记录顶点是否已被访问

// 使用Prim算法求解最小生成树
void prim(int s) {
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // 存储每个顶点到已选中顶点集合的最短距离
    fill(dist, dist + MAXN, INF);
    dist[s] = 0;
    pq.push(make_pair(0, s));
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].to;
            int w = G[u][i].weight;
            if (!visited[v] && w < dist[v]) {
                dist[v] = w;
                pq.push(make_pair(dist[v], v));
            }
        }
    }
}

int main() {
    int n, m;  // 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));
    }
    prim(1);  // 从顶点1开始求解最小生成树
    int ans = 0;  // 最小生成树的权值和
    for (int i = 1; i <= n; i++) {
        if (dist[i] != INF) ans += dist[i];
    }
    cout << ans << endl;
    return 0;
}

其中，使用了STL中的`priority_queue`（优先队列）来实现Prim算法中的最小堆。`pair<int, int>`表示每个节点到已选择节点集合的距离和节点编号，`vector<pair<int, int>>`表示存储所有节点到已选择节点集合的距离和节点编号的容器，`greater<pair<int, int>>`表示按照第一个元素（距离）从小到大的方式排序。