C语言最小生成树构造（10分）题目内容：某地对偏远地区实行“村村通”工程，目标是使整个地区任何两个村落间都可以实现快速交通（但不一定有直接的快速道路相连，只要互相间接通过快速路可达即可）。现得到拟修建道路的费用，现请你编写程序，计算出全地区畅通需要的最低成本。输入格式：输入的第一行给出村庄数目N (1≤N≤20)和拟修建的道路数M接下来的M行对应修建每条村庄间道路的成本，每行给出3个正整数，分别是两个村庄的编号（从1编号到N），此两村庄间道路的成本。输出格式：输出需修建的道路，按prim算法从编号1开始得到的顺序，输出每条路，每行输出一条道路，形式如：道路1编号,道路2编号,费用。(编号小的放前面，编号大的放后面，逗号为英文状态下的逗号)输入样例：4 61 2 11 3 41 4 12 3 32 4 23 4 5输出样例：1,2,11,4,1

以下是 C 语言实现的 Prim 算法求解最小生成树的代码，供您参考：

#include <stdio.h>
#include <limits.h>

#define MAXN 20
#define INF INT_MAX

int G[MAXN][MAXN];  // 图的邻接矩阵
int dist[MAXN];     // 记录每个点与生成树的距离
int path[MAXN];     // 记录每个点的前驱
int n, m;

// Prim 算法求最小生成树
void Prim()
{
    int i, j, k;
    int min, u;

    // 初始化距离和前驱
    for (i = 0; i < n; i++) {
        dist[i] = G[0][i];
        path[i] = 0;
    }

    // 依次加入 n-1 条边
    for (i = 1; i < n; i++) {
        min = INF;
        u = -1;

        // 找到距离生成树最近的点
        for (j = 0; j < n; j++) {
            if (dist[j] < min && dist[j] != 0) {
                min = dist[j];
                u = j;
            }
        }

        // 找不到距离生成树最近的点，退出循环
        if (u == -1) {
            break;
        }

        // 输出当前加入生成树的边
        printf("%d,%d,%d\n", path[u]+1, u+1, min);

        // 将 u 加入生成树
        dist[u] = 0;

        // 更新距离和前驱
        for (k = 0; k < n; k++) {
            if (dist[k] > G[u][k]) {
                dist[k] = G[u][k];
                path[k] = u;
            }
        }
    }
}

int main()
{
    int i, j, a, b, c;

    // 初始化邻接矩阵
    for (i = 0; i < MAXN; i++) {
        for (j = 0; j < MAXN; j++) {
            G[i][j] = INF;
        }
    }

    // 读入图的信息
    scanf("%d%d", &n, &m);
    for (i = 0; i < m; i++) {
        scanf("%d%d%d", &a, &b, &c);
        G[a-1][b-1] = G[b-1][a-1] = c;
    }

    // 调用 Prim 算法求解最小生成树
    Prim();

    return 0;
}

输入格式：

第一行两个正整数 $N$ 和 $M$，表示村庄数目和拟修建的道路数。

接下来 $M$ 行，每行三个正整数 $a$，$b$ 和 $c$，表示村庄 $a$ 和 $b$ 之间修建道路的成本为 $c$。

输出格式：

按照 Prim 算法从编号 $1$ 开始得到的顺序，输出每条路，每行输出一条道路，形式如：道路1编号,道路2编号,费用。(编号小的放前面，编号大的放后面，逗号为英文状态下的逗号)

注意：

- 本题中村庄的编号从 $1$ 开始，而在程序中数组下标从 $0$ 开始，因此需要将输入输出中的村庄编号减 $1$。
- 本题中规定输出的道路编号按照从小到大的顺序输出，因此需要加上 $1$。
- 本题中规定输出的逗号为英文状态下的逗号，因此需要注意输出格式。