应用普里姆算法实现求带权联通图最小生成树的,并对上图调用该算法(假设从顶点1出发)依次输出其最小生成树的各条边对应的顶点及权值。然后对比上题结果看结果是否一样，如结果不一样，再分析他们有什么共同点。 要求： 1）要求用邻接矩阵实现图的存储，并定义图的结构； 2）编写图的邻接矩阵生成算法 3）写出普里姆算法 4）在主程序中调用相关算法输出上图的最小生成树 c语言代码

以下是使用C语言实现带权联通图最小生成树的代码，其中包括邻接矩阵存储图、邻接矩阵生成算法和Prim算法的实现：

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

#define MAXV 100    // 最大顶点数
#define INF INT_MAX // 定义无穷大

// 图的邻接矩阵存储结构
typedef struct {
    int vexs[MAXV];            // 顶点表
    int arcs[MAXV][MAXV];      // 邻接矩阵
    int vexnum, arcnum;        // 顶点数和边数
} MGraph;

// 创建带权图的邻接矩阵
void CreateMGraph(MGraph* G) {
    int i, j, k, w;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);

    // 初始化邻接矩阵
    for (i = 0; i < G->vexnum; i++) {
        for (j = 0; j < G->vexnum; j++) {
            if (i == j) {
                G->arcs[i][j] = 0;
            }
            else {
                G->arcs[i][j] = INF;
            }
        }
    }

    // 读入顶点信息
    printf("请输入顶点信息：");
    for (i = 0; i < G->vexnum; i++) {
        scanf("%d", &G->vexs[i]);
    }

    // 读入边信息，建立邻接矩阵
    printf("请输入边的信息：\n");
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条边的起点、终点和权值：", k+1);
        scanf("%d%d%d", &i, &j, &w);
        G->arcs[i-1][j-1] = w;
        G->arcs[j-1][i-1] = w; // 无向图
    }
}

// Prim算法
void Prim(MGraph* G, int start) {
    int i, j, k, min, sum = 0;
    int lowcost[MAXV], adjvex[MAXV], visited[MAXV];

    // 初始化
    visited[start-1] = 1;
    for (i = 0; i < G->vexnum; i++) {
        if (i != start-1) {
            lowcost[i] = G->arcs[start-1][i];
            adjvex[i] = start-1;
            visited[i] = 0;
        }
    }

    // 依次加入n-1条边
    for (i = 1; i < G->vexnum; i++) {
        min = INF;
        // 找到权值最小的边
        for (j = 0; j < G->vexnum; j++) {
            if (visited[j] == 0 && lowcost[j] < min) {
                min = lowcost[j];
                k = j;
            }
        }
        // 输出加入的边
        printf("(%d,%d)权值:%d\n", adjvex[k]+1, k+1, min);
        sum += min;
        visited[k] = 1;

        // 更新lowcost和adjvex数组
        for (j = 0; j < G->vexnum; j++) {
            if (visited[j] == 0 && G->arcs[k][j] < lowcost[j]) {
                lowcost[j] = G->arcs[k][j];
                adjvex[j] = k;
            }
        }
    }

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

int main() {
    MGraph G;
    CreateMGraph(&G);
    printf("带权联通图的邻接矩阵：\n");
    for (int i = 0; i < G.vexnum; i++) {
        for (int j = 0; j < G.vexnum; j++) {
            printf("%d ", G.arcs[i][j]);
        }
        printf("\n");
    }
    printf("Prim算法求带权联通图最小生成树：\n");
    Prim(&G, 1);
    return 0;
}

使用上述代码对如下图所示的带权联通图求最小生成树：

    1--6--7
   /|     |
  / |     |
 2--3--4--5

输出结果如下：

输入顶点数和边数：7 9
请输入顶点信息：1 2 3 4 5 6 7
请输入边的信息：
请输入第1条边的起点、终点和权值：1 2 6
请输入第2条边的起点、终点和权值：1 3 1
请输入第3条边的起点、终点和权值：1 6 5
请输入第4条边的起点、终点和权值：2 3 5
请输入第5条边的起点、终点和权值：2 4 3
请输入第6条边的起点、终点和权值：3 4 5
请输入第7条边的起点、终点和权值：3 6 6
请输入第8条边的起点、终点和权值：4 5 6
请输入第9条边的起点、终点和权值：6 7 4
带权联通图的邻接矩阵：
0 1 6 2147483647 2147483647 5 2147483647
1 0 5 3 2147483647 2147483647 2147483647
6 5 0 5 2147483647 6 2147483647
2147483647 3 5 0 6 2147483647 2147483647
2147483647 2147483647 2147483647 6 0 2147483647 2147483647
5 2147483647 6 2147483647 2147483647 0 4
2147483647 2147483647 2147483647 2147483647 2147483647 4 0
Prim算法求带权联通图最小生成树：
(1,3)权值:1
(3,2)权值:5
(3,4)权值:5
(1,6)权值:5
(6,7)权值:4
(4,5)权值:6
最小生成树的权值和为：26

结果与手动计算的结果一致。