用 Prim 算法求解给定图的最小生成树的代码

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

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

const int MAXN = 1000; // 最大顶点数
int n, m; // 顶点数和边数
int g[MAXN][MAXN]; // 图的邻接矩阵表示
int dist[MAXN]; // 存储顶点到当前最小生成树的距离
bool vis[MAXN]; // 标记顶点是否已加入最小生成树

int prim() {
    int res = 0; // 最小生成树的权值和
    fill(dist, dist + n, INT_MAX);
    dist[0] = 0;
    for (int i = 0; i < n; i++) {
        int u = -1;
        for (int j = 0; j < n; j++) {
            if (!vis[j] && (u == -1 || dist[j] < dist[u])) {
                u = j;
            }
        }
        vis[u] = true;
        if (i != 0 && dist[u] == INT_MAX) {
            return -1; // 无法构成生成树
        }
        if (i != 0) {
            res += dist[u];
        }
        for (int v = 0; v < n; v++) {
            if (!vis[v] && g[u][v] != -1 && g[u][v] < dist[v]) {
                dist[v] = g[u][v];
            }
        }
    }
    return res;
}

int main() {
    cin >> n >> m;
    memset(g, -1, sizeof(g));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u][v] = g[v][u] = w;
    }
    int res = prim();
    if (res == -1) {
        cout << "无法构成生成树" << endl;
    } else {
        cout << "最小生成树的权值和为：" << res << endl;
    }
    return 0;
}

其中，`g[u][v]` 表示顶点 `u` 和 `v` 之间的边的权值，如果 `g[u][v]` 为 `-1`，则表示不存在这条边。在代码中，我们使用 `dist` 数组存储顶点到当前最小生成树的距离，使用 `vis` 数组标记顶点是否已加入最小生成树。算法的时间复杂度为 $O(n^2)$，其中 $n$ 为顶点数。