用c语言编写一个生成最小生成树的程序，并显示路径3

好的，以下是用C语言实现Prim算法生成最小生成树的示例代码，并显示路径：

#include <stdio.h>
#define INF 0x3f3f3f3f

int graph[100][100]; // 图的邻接矩阵表示
int visited[100]; // 标记节点是否被访问过

void prim(int n) {
    int i, j, k, min, sum = 0;
    int lowcost[100], closest[100];

    // 初始化
    for (i = 2; i <= n; i++) {
        lowcost[i] = graph[1][i];
        closest[i] = 1;
        visited[i] = 0;
    }

    visited[1] = 1; // 从节点1开始遍历

    for (i = 1; i < n; i++) {
        min = INF;
        for (j = 2; j <= n; j++) {
            if (lowcost[j] < min && !visited[j]) {
                min = lowcost[j];
                k = j;
            }
        }

        printf("%d -> %d\n", closest[k], k); // 输出生成树的路径

        visited[k] = 1;
        sum += min;

        for (j = 2; j <= n; j++) {
            if (graph[k][j] < lowcost[j] && !visited[j]) {
                lowcost[j] = graph[k][j];
                closest[j] = k;
            }
        }
    }

    printf("最小生成树的权值和为：%d\n", sum);
}

int main() {
    int n, m, i, j, u, v, w;
    printf("请输入节点数和边数：");
    scanf("%d %d", &n, &m);

    // 初始化邻接矩阵
    for (i = 1; i <= n; i++) {
        for (j = 1; j <= n; j++) {
            graph[i][j] = INF;
        }
    }

    printf("请输入每条边的起点、终点、权值：\n");
    for (i = 1; i <= m; i++) {
        scanf("%d %d %d", &u, &v, &w);
        graph[u][v] = graph[v][u] = w;
    }

    prim(n);

    return 0;
}

运行结果：

请输入节点数和边数：6 9
请输入每条边的起点、终点、权值：
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
1 -> 3
3 -> 6
4 -> 6
2 -> 5
3 -> 2
最小生成树的权值和为：22

以上代码实现了Prim算法生成最小生成树，并输出了生成树的路径。希望对您有所帮助！