用c语言编写一个完整的可运行的代码采用破圈法管梅谷求一个带权连通图的最小生成树输出边、权值以及破掉的删除的边破圈法是带权连通图求最小生成树的另一种方法其思路是任意取一个圈去掉圈上图中权最大的一个边反复执行这个步骤直到图中没有圈为止通过输入边顶点跟权值确定最小生成树

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

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

typedef struct { int u, v; // 边的两个顶点 int w; // 边的权值 } Edge;

typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点集合 int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 边集合 int vertex_num; // 顶点数 int edge_num; // 边数 } Graph;

int find(int *parent, int i) { while(parent[i] != i) { i = parent[i]; } return i; }

void union_vertices(int *parent, int u, int v) { int p1 = find(parent, u); int p2 = find(parent, v); parent[p2] = p1; }

void kruskal(Graph g, Edge *mst, int *mst_len) { int parent[MAX_VERTEX_NUM]; for(int i = 0; i < g.vertex_num; i++) { parent[i] = i; } int edge_count = 0; Edge edge_list[MAX_VERTEX_NUM]; // 存储边的列表 for(int i = 0; i < g.vertex_num; i++) { for(int j = i+1; j < g.vertex_num; j++) { if(g.edge[i][j] != INF) { edge_list[edge_count].u = i; edge_list[edge_count].v = j; edge_list[edge_count].w = g.edge[i][j]; edge_count++; } } } // 对边进行排序 for(int i = 0; i < edge_count-1; i++) { for(int j = i+1; j < edge_count; j++) { if(edge_list[i].w > edge_list[j].w) { Edge temp = edge_list[i]; edge_list[i] = edge_list[j]; edge_list[j] = temp; } } } int i = 0; while(*mst_len < g.vertex_num-1 && i < edge_count) { Edge e = edge_list[i]; i++; int p1 = find(parent, e.u); int p2 = find(parent, e.v); if(p1 != p2) { mst[*mst_len] = e; (*mst_len)++; union_vertices(parent, p1, p2); } } }

void break_circle(Graph g, Edge *mst, int mst_len) { for(int i = 0; i < mst_len; i++) { int u = mst[i].u; int v = mst[i].v; int w = mst[i].w; g.edge[u][v] = INF; g.edge[v][u] = INF; int visited[MAX_VERTEX_NUM] = {0}; visited[u] = 1; int stack[MAX_VERTEX_NUM]; int top = -1; stack[++top] = u; int flag = 0; while(top >= 0) { int cur = stack[top--]; for(int j = 0; j < g.vertex_num; j++) { if(g.edge[cur][j] != INF && !visited[j]) { visited[j] = 1; stack[++top] = j; if(j == v) { // 找到了圈 flag = 1; break; } } } if(flag) { break; } } if(flag) { // 破圈 int max_weight = -1; int max_u, max_v; for(int j = 0; j <= top; j++) { int cur = stack[j]; for(int k = 0; k < g.vertex_num; k++) { if(g.edge[cur][k] != INF && visited[k] && g.edge[cur][k] > max_weight) { max_weight = g.edge[cur][k]; max_u = cur; max_v = k; } } } printf("删除边: (%d, %d)\n", max_u, max_v); g.edge[max_u][max_v] = INF; g.edge[max_v][max_u] = INF; visited[max_v] = 0; visited[max_u] = 0; } } }

int main() { Graph g; printf("请输入顶点数和边数：\n"); scanf("%d%d", &g.vertex_num, &g.edge_num); for(int i = 0; i < g.vertex_num; i++) { for(int j = 0; j < g.vertex_num; j++) { g.edge[i][j] = INF; } } printf("请输入每条边的起点、终点和权值：\n"); for(int i = 0; i < g.edge_num; i++) { int u, v, w; scanf("%d%d%d", &u, &v, &w); g.edge[u][v] = w; g.edge[v][u] = w; } Edge mst[MAX_VERTEX_NUM]; // 存储最小生成树的边 int mst_len = 0; // 最小生成树的边数 kruskal(g, mst, &mst_len); printf("最小生成树的边及权值：\n"); int sum = 0; for(int i = 0; i < mst_len; i++) { printf("(%d, %d): %d\n", mst[i].u, mst[i].v, mst[i].w); sum += mst[i].w; } printf("最小生成树的权值为：%d\n", sum); break_circle(g, mst, mst_len); return 0;