prim算法实现c语言

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

#include <stdio.h>
#include <stdlib.h>
#define INF 32767 // 定义正无穷

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

void prim(Graph g, int start) {
    int i, j, k, min;
    int *lowcost = (int*)malloc(sizeof(int)*g.n); // 记录U到V-U的最小距离
    int *closest = (int*)malloc(sizeof(int)*g.n); // 记录当前最小生成树中与顶点i最近的顶点
    for (i = 1; 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() {
    int i, j;
    Graph g;
    g.n = 6;
    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;
        }
    }
    g.edges[0][1] = g.edges[1][0] = 6;
    g.edges[0][2] = g.edges[2][0] = 1;
    g.edges[0][3] = g.edges[3][0] = 5;
    g.edges[1][2] = g.edges[2][1] = 5;
    g.edges[1][4] = g.edges[4][1] = 3;
    g.edges[2][3] = g.edges[3][2] = 5;
    g.edges[2][4] = g.edges[4][2] = 6;
    g.edges[2][5] = g.edges[5][2] = 4;
    g.edges[3][5] = g.edges[5][3] = 2;
    g.edges[4][5] = g.edges[5][4] = 6;
    prim(g, 0);
    return 0;
}