C语言实现：破圈法求解带权连通图的最小生成树及破圈边

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

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

typedef struct { int from; // 起点 int to; // 终点 int weight; // 权值 } Edge;

typedef struct { int vertex[MAX_VERTEX_NUM]; // 顶点数组 int matrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵 int vertex_num; // 顶点数 int edge_num; // 边数 } Graph;

int find(int *parent, int i) { if (parent[i] == -1) { return i; } return find(parent, parent[i]); }

void unionSet(int *parent, int x, int y) { int xset = find(parent, x); int yset = find(parent, y); parent[xset] = yset; }

int cmp(const void *a, const void *b) { Edge *e1 = (Edge *)a; Edge *e2 = (Edge *)b; return e1->weight - e2->weight; }

// Kruskal算法求解最小生成树 void kruskal(Graph *graph, Edge *result) { int *parent = (int *)malloc(graph->vertex_num * sizeof(int)); for (int i = 0; i < graph->vertex_num; i++) { parent[i] = -1; } qsort(graph->matrix, graph->edge_num, sizeof(Edge), cmp); int i = 0; // result数组下标 int j = 0; // matrix数组下标 while (i < graph->vertex_num - 1) { Edge next_edge = graph->matrix[j++]; int x = find(parent, next_edge.from); int y = find(parent, next_edge.to); if (x != y) { result[i++] = next_edge; unionSet(parent, x, y); } } free(parent); }

// 破圈法求解最小生成树并记录破圈边 void breakCircle(Graph *graph, Edge *result, Edge *break_edge) { // 初始化parent数组 int *parent = (int *)malloc(graph->vertex_num * sizeof(int)); for (int i = 0; i < graph->vertex_num; i++) { parent[i] = -1; } // 构建初始生成树 int i = 0; int j = 0; while (i < graph->vertex_num - 1) { Edge next_edge = graph->matrix[j++]; int x = find(parent, next_edge.from); int y = find(parent, next_edge.to); if (x != y) { result[i++] = next_edge; unionSet(parent, x, y); } } // 寻找圈并破圈 while (1) { int max_weight = -1; int max_edge_index = -1; // 找到权值最大的边 for (int k = 0; k < graph->edge_num; k++) { if (find(parent, graph->matrix[k].from) != find(parent, graph->matrix[k].to)) { if (graph->matrix[k].weight > max_weight) { max_weight = graph->matrix[k].weight; max_edge_index = k; } } } // 如果找不到圈，则退出循环 if (max_edge_index == -1) { break; } // 破圈 Edge break_edge_tmp = graph->matrix[max_edge_index]; graph->matrix[max_edge_index].weight = INF; // 重新构建生成树 i = 0; j = 0; while (i < graph->vertex_num - 1) { Edge next_edge = graph->matrix[j++]; int x = find(parent, next_edge.from); int y = find(parent, next_edge.to); if (x != y) { result[i++] = next_edge; unionSet(parent, x, y); } } // 判断是否连通 int flag = 1; for (int k = 1; k < graph->vertex_num; k++) { if (find(parent, k) != find(parent, 0)) { flag = 0; break; } } // 如果不连通，则恢复边权，继续寻找圈 if (!flag) { graph->matrix[max_edge_index] = break_edge_tmp; } // 如果连通，则记录破圈的边并退出循环 else { *break_edge = break_edge_tmp; break; } } free(parent); }

int main() { Graph graph; Edge result[MAX_VERTEX_NUM]; Edge break_edge; printf('请输入顶点数和边数：\n'); scanf('%d %d', &graph.vertex_num, &graph.edge_num); printf('请输入每条边的起点、终点和权值：\n'); for (int i = 0; i < graph.edge_num; i++) { int from, to, weight; scanf('%d %d %d', &from, &to, &weight); graph.matrix[i].from = from; graph.matrix[i].to = to; graph.matrix[i].weight = weight; } // 求最小生成树 kruskal(&graph, result); printf('最小生成树为：\n'); int total_weight = 0; for (int i = 0; i < graph.vertex_num - 1; i++) { printf('%d -> %d : %d\n', result[i].from, result[i].to, result[i].weight); total_weight += result[i].weight; } printf('总权值为：%d\n', total_weight); // 破圈法 breakCircle(&graph, result, &break_edge); printf('破圈后删除的边为：%d -> %d : %d\n', break_edge.from, break_edge.to, break_edge.weight); return 0; }