使用c语言普利姆算法计算最小生成树代码

好的，下面是使用 C 语言实现的普利姆算法代码示例，假设我们有一个邻接矩阵 graph 表示图的结构和边的权值：

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

#define MAX_VERTICES 100
#define INF 1000000

int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];

typedef struct {
    int u;
    int v;
    int weight;
} Edge;

Edge mst[MAX_VERTICES-1];

void prim(int n) {
    int i, j, u, v, min_weight;
    int num_edges = 0;
    
    // 初始化 visited 数组和最小生成树集合
    for (i = 0; i < n; i++) {
        visited[i] = false;
    }
    
    visited[0] = true;
    
    // 遍历所有节点
    while (num_edges < n-1) {
        // 找到当前与 visited 集合相邻的边中权值最小的边
        min_weight = INF;
        for (i = 0; i < n; i++) {
            if (visited[i]) {
                for (j = 0; j < n; j++) {
                    if (!visited[j] && graph[i][j] != 0 && graph[i][j] < min_weight) {
                        min_weight = graph[i][j];
                        u = i;
                        v = j;
                    }
                }
            }
        }
        
        // 将其加入最小生成树集合
        visited[v] = true;
        mst[num_edges].u = u;
        mst[num_edges].v = v;
        mst[num_edges].weight = min_weight;
        num_edges++;
    }
}

int main() {
    int i, j, n;
    
    // 读入图的结构和边的权值
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    
    // 计算最小生成树
    prim(n);
    
    // 输出最小生成树
    for (i = 0; i < n-1; i++) {
        printf("(%d, %d) - %d\n", mst[i].u, mst[i].v, mst[i].weight);
    }
    
    return 0;
}

在这段代码中，我们使用了一个结构体 Edge 来存储边的信息，mst 数组用于存储最小生成树的边。在遍历过程中，我们不断寻找当前与 visited 集合相邻的边中权值最小的边，将其加入最小生成树集合中，并标记其连接的节点为 visited。最终输出 mst 数组中的所有边即可。