用c语言编写一个完整的可运行的代码采用破圈法求一个带权连通图的最小生成树目的：深入了解图的复杂操作、图遍历算法和最小生成树的概念以及最小生成树的构造运算。内容：编写一个程序采用破圈法求一个带权连通图的最小生成树破圈法是带权连通图求最小生成树的另一种方法其思路是任意取一个圈去掉圈上图中权最大的一个边反复执行这个步骤直到图中没有圈为止

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

#define MAX_VERTEX_NUM 100 // 最大顶点数 #define INF 65535 // 无穷大

// 图的邻接矩阵表示 typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点数组 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边的数组 int vertex_num, edge_num; // 顶点数和边数 } Graph;

// 创建图 void create_graph(Graph *G) { int i, j, k, v, w; printf("请输入顶点数和边数："); scanf("%d%d", &G->vertex_num, &G->edge_num); // 初始化邻接矩阵 for (i = 0; i < G->vertex_num; i++) { for (j = 0; j < G->vertex_num; j++) { if (i == j) { G->edge[i][j] = 0; } else { G->edge[i][j] = INF; } } } // 输入每条边的信息 for (k = 0; k < G->edge_num; k++) { printf("请输入第%d条边的起点、终点和权值：", k + 1); scanf("%d%d%d", &v, &w, &i); G->edge[v][w] = i; G->edge[w][v] = i; // 无向图 } }

// 破圈法求最小生成树 void prim(Graph *G) { int i, j, k, min, sum = 0; int lowcost[MAX_VERTEX_NUM], closest[MAX_VERTEX_NUM], visited[MAX_VERTEX_NUM]; // 初始化 for (i = 1; i < G->vertex_num; i++) { lowcost[i] = G->edge[0][i]; closest[i] = 0; visited[i] = 0; } visited[0] = 1; // 求最小生成树 for (i = 1; i < G->vertex_num; i++) { min = INF; j = 1; // 找到距离当前生成树最近的顶点 while (j < G->vertex_num) { if (!visited[j] && lowcost[j] < min) { min = lowcost[j]; k = j; } j++; } printf("(%d,%d)\n", closest[k], k); sum += min; visited[k] = 1; // 更新距离 for (j = 1; j < G->vertex_num; j++) { if (!visited[j] && G->edge[k][j] < lowcost[j]) { lowcost[j] = G->edge[k][j]; closest[j] = k; } } } printf("最小生成树的权值为：%d\n", sum); }

int main() { Graph G; create_graph(&G); prim(&G); return 0;