C语言实现最小生成树prim算法

Prim算法是一种求解加权连通图的最小生成树的贪心算法。C语言实现最小生成树Prim算法的步骤如下：
1. 定义图结构体，包括节点数、边数和邻接矩阵。
2. 初始化邻接矩阵，将非连通节点的边权重设为无穷大。
3. 定义一个数组存储每个节点到已选择节点集合的最小边权值。
4. 定义一个数组存储每个节点是否已经被选择。
5. 选择一个起始节点，将其加入已选择节点集合中，并更新其邻接节点的最小边权值。
6. 重复执行以下步骤，直到已选择节点集合包含所有节点：
1) 从未选择节点中选出到已选择节点集合的最小边权值最小的节点。
2) 将该节点加入已选择节点集合，并更新其邻接节点的最小边权值。
7. 最后得到的已选择节点集合和它们之间的边就是最小生成树。

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

// 定义图结构体
struct Graph {
    int n; // 节点数
    int m; // 边数
    int w[N][N]; // 邻接矩阵
};

// Prim算法求解最小生成树
void Prim(Graph g, int start) {
    int i, j, k, min, sum = 0;
    int lowcost[N], closest[N], vis[N];

    // 初始化数据
    for (i = 1; i <= g.n; i++) {
        lowcost[i] = g.w[start][i];
        closest[i] = start;
        vis[i] = 0;
    }
    vis[start] = 1;

    // 执行n-1次循环，得到n-1条边
    for (i = 1; i < g.n; i++) {
        min = INF;
        // 找出到已选择节点集合的最小边权值
        for (j = 1; j <= g.n; j++) {
            if (!vis[j] && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        vis[k] = 1;
        sum += min;

        // 更新未选择节点的最小边权值
        for (j = 1; j <= g.n; j++) {
            if (!vis[j] && g.w[k][j] < lowcost[j]) {
                lowcost[j] = g.w[k][j];
                closest[j] = k;
            }
        }
    }

    // 输出最小生成树
    for (i = 1; i <= g.n; i++) {
        if (closest[i] != start) {
            printf("%d-%d\n", closest[i], i);
        }
    }
}