prim算法的c语言实现

以下是prim算法的C语言实现：

#include <stdio.h>
#include <stdlib.h>
#define INF 32767 //INF表示∞

typedef struct {
    int n; //顶点数
    int **edges; //邻接矩阵
}Graph;

void CreateGraph(Graph *g) { //创建邻接矩阵
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &g->n, &k);
    g->edges = (int**)malloc(sizeof(int*)*g->n);
    for (i = 0; i < g->n; i++) {
        g->edges[i] = (int*)malloc(sizeof(int)*g->n);
    }
    for (i = 0; i < g->n; i++) { //初始化邻接矩阵
        for (j = 0; j < g->n; j++) {
            g->edges[i][j] = INF;
        }
    }
    printf("请输入每条边的起点、终点和权值：\n");
    for (i = 0; i < k; i++) { //读入边
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        g->edges[a][b] = w;
        g->edges[b][a] = w;
    }
}

void Prim(Graph g, int start) { //Prim算法
    int i, j, k, min;
    int *lowcost = (int*)malloc(sizeof(int)*g.n); //记录U到V-U的最小权值
    int *closest = (int*)malloc(sizeof(int)*g.n); //记录当前最小生成树中与V-U相邻的顶点
    for (i = 0; i < g.n; i++) { //初始化lowcost和closest数组
        lowcost[i] = g.edges[start][i];
        closest[i] = start;
    }
    lowcost[start] = 0; //将start加入U
    for (i = 1; i < g.n; i++) { //循环n-1次，每次找出一个顶点加入U
        min = INF;
        for (j = 0; j < g.n; j++) { //在(V-U)中找出离U最近的顶点k
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j; //k记录最近顶点的编号
            }
        }
        printf("边(%d,%d)权为:%d\n", closest[k], k, min);
        lowcost[k] = 0; //标记k已经加入U
        for (j = 0; j < g.n; j++) { //对(V-U)中的顶点j进行调整
            if (g.edges[k][j] < lowcost[j]) {
                lowcost[j] = g.edges[k][j];
                closest[j] = k; //修改数组lowcost和closest
            }
        }
    }
}

int main() {
    Graph g;
    CreateGraph(&g);
    Prim(g, 2); //从顶点2开始构造最小生成树
    return 0;
}