Prim算法代码C语言

以下是Prim算法的C语言实现代码：

#include <stdio.h>
#include <stdbool.h>

#define INF 0x3f3f3f3f
#define MAXN 1000

int graph[MAXN][MAXN];  // 图的邻接矩阵
int dist[MAXN];         // 到生成树的最短距离
bool vis[MAXN];         // 节点是否已访问
int n;                  // 节点数

int prim(int start) {
    int ans = 0;         // 最小生成树的权值和
    for (int i = 1; i <= n; i++) {
        dist[i] = INF;
        vis[i] = false;
    }
    dist[start] = 0;
    for (int i = 1; i <= n; i++) {
        int u = 0;
        for (int j = 1; j <= n; j++) {
            if (!vis[j] && (u == 0 || dist[j] < dist[u])) {
                u = j;
            }
        }
        vis[u] = true;
        ans += dist[u];
        for (int v = 1; v <= n; v++) {
            if (!vis[v] && graph[u][v] < dist[v]) {
                dist[v] = graph[u][v];
            }
        }
    }
    return ans;
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    int start = 1;
    printf("%d\n", prim(start));
    return 0;
}

其中，`graph` 是图的邻接矩阵，`dist` 数组存储每个节点到当前生成树的最短距离，`vis` 数组标记每个节点是否已经访问过。`prim` 函数返回最小生成树的权值和。