使用prim算法求带权无向图的最小生成树 c语言

下面是使用Prim算法求带权无向图的最小生成树的C语言实现：

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

#define MAXV 1000 // 最大顶点数

typedef struct {
    int adj[MAXV][MAXV]; // 邻接矩阵
    int n; // 顶点数
} Graph;

int prim(Graph* g) {
    int vis[MAXV] = {0}; // 标记顶点是否已被加入生成树
    int dist[MAXV]; // 存储每个顶点到生成树的最短距离
    int parent[MAXV]; // 存储每个顶点在生成树中的父节点
    int i, j, u, min_dist, min_index, sum = 0;

    // 初始化dist数组和parent数组
    for (i = 0; i < g->n; ++i) {
        dist[i] = INT_MAX;
        parent[i] = -1;
    }

    // 从0号顶点开始构建生成树
    dist[0] = 0;
    u = 0;

    // 执行n-1次循环，每次将一个顶点加入生成树
    for (i = 0; i < g->n-1; ++i) {
        vis[u] = 1; // 将u加入生成树
        min_dist = INT_MAX;
        min_index = -1;

        // 更新dist数组和parent数组
        for (j = 0; j < g->n; ++j) {
            if (!vis[j] && g->adj[u][j] < dist[j]) {
                dist[j] = g->adj[u][j];
                parent[j] = u;
            }
            if (!vis[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_index = j;
            }
        }

        // 更新sum
        sum += min_dist;

        // 将与min_index相连的顶点的dist值更新为新的最短距离
        u = min_index;
    }
    return sum;
}

int main() {
    Graph g = {
        {
            {0, 7, 0, 5, 0, 0},
            {7, 0, 8, 9, 7, 0},
            {0, 8, 0, 0, 5, 0},
            {5, 9, 0, 0, 15, 6},
            {0, 7, 5, 15, 0, 8},
            {0, 0, 0, 6, 8, 0}
        },
        6 // 顶点数
    };
    printf("Minimum weight of the MST: %d\n", prim(&g));
    return 0;
}

在本例中，我们使用邻接矩阵存储图，并通过结构体`Graph`来表示。在`prim`函数中，我们使用一个`vis`数组来标记哪些顶点已被加入生成树，使用`dist`数组来存储每个顶点到生成树的最短距离，使用`parent`数组来存储每个顶点在生成树中的父节点。在循环中，我们首先将0号顶点加入生成树，然后执行n-1次循环，每次将一个顶点加入生成树。在每次循环中，我们更新`dist`数组和`parent`数组，并找到未被加入生成树的顶点中距离生成树最近的顶点，将其加入生成树。最后，我们将所有边的权重相加即得到最小生成树的权重。