c语言代码实现加权图的建立和prim算法求最小生成树

以下是使用 C 语言实现加权图的建立和 Prim 算法求最小生成树的代码：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_VERTICES 100
#define INF INT_MAX

int n; // 图的顶点数
int dist[MAX_VERTICES]; // 存放从已经包含在最小生成树中的顶点到其它顶点的最短距离
int visited[MAX_VERTICES]; // 标记顶点是否已经包含在最小生成树中
int graph[MAX_VERTICES][MAX_VERTICES]; // 存放图的邻接矩阵

void prim(int start) {
    int i, j, k;
    int min;
    int u;

    // 初始化
    for (i = 0; i < n; i++) {
        dist[i] = INF;
        visited[i] = 0;
    }
    dist[start] = 0;

    for (i = 0; i < n; i++) {
        min = INF;
        for (j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min) {
                min = dist[j];
                u = j;
            }
        }
        visited[u] = 1;
        for (k = 0; k < n; k++) {
            if (!visited[k] && graph[u][k] < dist[k]) {
                dist[k] = graph[u][k];
            }
        }
    }
}

int main() {
    int i, j;

    // 读入图的顶点数和边数
    int m;
    scanf("%d%d", &n, &m);

    // 初始化图的邻接矩阵
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            graph[i][j] = INF;
        }
    }

    // 读入每条边的信息，并更新邻接矩阵
    int u, v, w;
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &u, &v, &w);
        graph[u][v] = w;
        graph[v][u] = w;
    }

    // 调用 Prim 算法求最小生成树
    prim(0);

    // 输出最小生成树的边权和
    int sum = 0;
    for (i = 0; i < n; i++) {
        sum += dist[i];
    }
    printf("%d\n", sum);

    return 0;
}

在上述代码中，`graph` 数组存放加权图的邻接矩阵，`dist` 数组存放从已经包含在最小生成树中的顶点到其它顶点的最短距离，`visited` 数组标记顶点是否已经包含在最小生成树中。`prim()` 函数使用 Prim 算法构造最小生成树。在主函数中，我们首先读入图的顶点数和边数，然后初始化图的邻接矩阵，接着读入每条边的信息，并更新邻接矩阵。最后调用 `prim()` 函数求最小生成树，并输出最小生成树的边权和。