prim算法构造最小生成树的c语言代码演示

Prim算法是一种构造最小生成树的贪心算法，具体实现步骤如下：
1. 创建一个空的最小生成树，将任意一个节点作为起始节点加入最小生成树中。
2. 遍历与已加入最小生成树的所有节点相邻的所有边，并找到其中权值最小的那条边所连接的节点，将该节点和边加入最小生成树中。
3. 重复执行步骤2，直到所有节点都被加入最小生成树为止。

下面是Prim算法的C语言代码演示：

#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
#define INF 0x3f3f3f3f

int graph[MAX][MAX];
int dist[MAX];
int visited[MAX];
int n, m;

void prim(int s) {
    for(int i = 1; i <= n; i++) {
        dist[i] = INF;      // 初始化所有距离为无穷大
        visited[i] = 0;     // 初始化所有节点为未访问状态
    }
    dist[s] = 0;            // 起始节点的距离为0

    for(int i = 1; i <= n; i++) {
        int u = 0, min = INF;
        for(int j = 1; j <= n; j++) {
            if(!visited[j] && dist[j] < min) {      // 找到未访问过的节点中距离最短的那个节点
                u = j;
                min = dist[j];
            }
        }
        visited[u] = 1;     // 标记该节点为已访问状态

        for(int v = 1; v <= n; v++) {
            if(!visited[v] && graph[u][v] < dist[v]) {      // 更新与u相邻的所有节点的距离
                dist[v] = graph[u][v];
            }
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);

    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            graph[i][j] = INF;
        }
    }

    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;
    }

    prim(1);

    int sum = 0;
    for(int i = 1; i <= n; i++) {
        sum += dist[i];
    }

    printf("最小生成树的权值和为：%d\n", sum);

    return 0;
}