Prim算法c语言实现

Prim算法是一种求解最小生成树的贪心算法，其C语言实现如下：

1. 首先定义一个函数Prim，参数为一个邻接矩阵图G和一个起始顶点v。
2. 初始化辅助数组lowcost和adjvex，其中lowcost[i]表示从集合U到顶点i的最小边权值，adjvex[i]表示顶点i在最小生成树中的父节点。
3. 将起始顶点v加入集合U，即将lowcost[v]赋值为0。
4. 迭代n-1次，每次找到一条从集合U到集合V-U的最小边，将其加入最小生成树中。
5. 在迭代过程中，更新lowcost和adjvex数组，以便下一次迭代时能够找到新的最小边。

具体实现细节可以参考下面的代码：

void Prim(MGraph *G, int v) {
    int i, j, k, adjvex[MaxSize], lowcost[MaxSize];
    // 初始化辅助数组lowcost和adjvex
    for (i = 0; i < G->vertexNum; i++) {
        lowcost[i] = G->edge[v][i];
        adjvex[i] = v;
    }
    lowcost[v] = 0; // 将顶点v加入集合U
    // 迭代n-1次
    for (k = 1; k < G->vertexNum; k++) {
        j = MinEdge(lowcost, G->vertexNum); // 寻找最短边的邻接点j
        printf("(%d, %d)%d ", j, adjvex[j], lowcost[j]); // 输出最小边
        lowcost[j] = 0; // 将j加入集合U
        // 调整数组lowcost和adjvex
        for (i = 0; i < G->vertexNum; i++) {
            if (G->edge[i][j] < lowcost[i]) {
                lowcost[i] = G->edge[i][j];
                adjvex[i] = j;
            }
        }
    }
}