prim最小生成树 c语言

以下是使用C语言实现Prim算法求解最小生成树的示例代码：

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

#define MAX_VERTICES 1000

int graph[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵表示的图
int visited[MAX_VERTICES]; // 标记已访问的节点

int prim(int n) {
    int min_weight = 0; // 最小权重
    int num_visited = 1; // 已访问的节点数量
    int u, v;

    visited[0] = 1; // 从节点0开始

    while (num_visited < n) {
        int min_dist = INT_MAX;

        // 遍历所有已访问的节点，找到到未访问节点的最短边
        for (int i = 0; i < num_visited; i++) {
            u = visited[i];
            for (int j = 0; j < n; j++) {
                if (!visited[j] && graph[u][j] && graph[u][j] < min_dist) {
                    min_dist = graph[u][j];
                    v = j;
                }
            }
        }

        visited[num_visited++] = v; // 将最短边的终点标记为已访问

        min_weight += min_dist; // 累加权重
    }

    return min_weight;
}

int main() {
    int n, m;

    scanf("%d %d", &n, &m);

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

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

    printf("%d\n", prim(n));

    return 0;
}

该示例代码中，使用邻接矩阵来表示图，使用visited数组来标记已访问的节点。在prim函数中，每次找到到未访问节点的最短边，并将最短边的终点标记为已访问，累加权重。最后返回累加的权重即为最小生成树的权重。