给出邻接矩阵表示的图的Prim算法

邻接矩阵表示的图的Prim算法如下：

#include <stdio.h>
#include <stdlib.h>
#include <limits.h> // 定义了INT_MAX常量

#define MAX_VERTEX_NUM 20 // 最大顶点数
#define INF INT_MAX // 定义正无穷

typedef struct {
    int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vexnum, arcnum; // 顶点数、边数
} MGraph;

MGraph* CreateMGraph(int vexnum, int arcnum); // 创建邻接矩阵图
void MiniSpanTree_Prim(MGraph* G, int u); // Prim算法

int main() {
    MGraph* G = CreateMGraph(6, 10);
    MiniSpanTree_Prim(G, 0);
    return 0;
}

MGraph* CreateMGraph(int vexnum, int arcnum) {
    MGraph* G = (MGraph*)malloc(sizeof(MGraph));
    G->vexnum = vexnum;
    G->arcnum = arcnum;
    for (int i = 0; i < vexnum; i++) {
        for (int j = 0; j < vexnum; j++) {
            if (i == j) {
                G->arcs[i][j] = 0; // 对角线上的元素为0
            } else {
                G->arcs[i][j] = INF; // 其余元素为正无穷
            }
        }
    }
    int v1, v2, w;
    for (int k = 0; k < arcnum; k++) {
        scanf("%d %d %d", &v1, &v2, &w);
        G->arcs[v1][v2] = w; // 有向图
        G->arcs[v2][v1] = w; // 无向图
    }
    return G;
}

void MiniSpanTree_Prim(MGraph* G, int u) {
    int lowcost[MAX_VERTEX_NUM]; // 存储当前生成树到每个非树顶点的最小边权值
    int closest[MAX_VERTEX_NUM]; // 存储当前生成树到每个非树顶点的最小边的起点
    int v = u;
    for (int i = 0; i < G->vexnum; i++) {
        if (i != v) {
            lowcost[i] = G->arcs[v][i]; // 初始化lowcost数组
            closest[i] = v; // 初始化closest数组
        }
    }
    for (int i = 1; i < G->vexnum; i++) { // 循环n-1次
        int min = INF;
        for (int j = 0; j < G->vexnum; j++) { // 找到lowcost数组中最小的值及其下标
            if (lowcost[j] != 0 && lowcost[j] < min) {
                min = lowcost[j];
                v = j;
            }
        }
        printf("(%d, %d)\n", closest[v], v); // 输出生成树中的一条边
        lowcost[v] = 0; // 标记为已经访问过
        for (int j = 0; j < G->vexnum; j++) { // 更新lowcost和closest数组
            if (lowcost[j] != 0 && G->arcs[v][j] < lowcost[j]) {
                lowcost[j] = G->arcs[v][j];
                closest[j] = v;
            }
        }
    }
}

注意，这里假设输入的图是无向图。如果输入的是有向图，需要将下面的注释打开：

// G->arcs[v2][v1] = w; // 无向图