用c语言编程实现prim算法

Prim算法是一种用于解决最小生成树问题的贪心算法，其基本思想是从图的一个顶点开始，逐步将与该顶点相连的最短边加入到生成树中，直到所有顶点都被加入。以下是用C语言编写Prim算法的基本步骤：

1. 定义一个数组dist[]，用于存储当前生成树中每个节点到树的距离，初始值为正无穷；
2. 定义一个数组visited[]，用于标记每个节点是否已经加入生成树中，初始值为false；
3. 选择一个起始节点，将其加入生成树中，并将dist[]数组对应位置的值设为0；
4. 重复以下步骤直到所有节点都被加入生成树中：
1) 遍历当前已经加入生成树中的节点，找出与之相连的所有节点中距离最短的那个节点；
2) 将该节点加入生成树中，并将dist[]数组对应位置的值设为该节点与当前生成树中最近节点之间的距离；
3) 将visited[]数组对应位置的值设为true；
5. 输出生成树。

下面是一份用C语言编写Prim算法的代码参考：

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

#define MAX_VERTICES 1000
#define INF 1000000

int n; // 顶点数
int adj[MAX_VERTICES][MAX_VERTICES]; // 图的邻接矩阵
bool visited[MAX_VERTICES]; // 记录每个顶点是否已经加入生成树
int dist[MAX_VERTICES]; // 记录当前生成树中每个节点到树的距离

void prim() {
    for (int i = 0; i < n; i++) {
        visited[i] = false;
        dist[i] = INF;
    }
    dist = 0; // 选择第一个顶点作为起始点
    for (int i = 0; i < n; i++) {
        int min_dist = INF, min_vertex;
        // 找到当前生成树中距离最短的顶点
        for (int j = 0; j < n; j++) {
            if (!visited[j] && dist[j] < min_dist) {
                min_dist = dist[j];
                min_vertex = j;
            }
        }
        visited[min_vertex] = true;
        // 更新与该顶点相邻的顶点到树的距离
        for (int j = 0; j < n; j++) {
            if (!visited[j] && adj[min_vertex][j] < dist[j]) {
                dist[j] = adj[min_vertex][j];
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    // 输入邻接矩阵
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &adj[i][j]);
        }
    }
    prim(); // 执行Prim算法
    // 输出最小生成树
    int sum_weight = 0;
    for (int i = 0; i < n; i++) {
        sum_weight += dist[i];
    }
    printf("The weight of minimum spanning tree is %d\n", sum_weight);
    return 0;
}