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

以下是一个可运行的C语言代码，实现了破圈法求带权连通图的最小生成树：

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

#define MAX_VERTICES 100 #define INFINITY INT_MAX

typedef struct { int u, v, weight; } Edge;

typedef struct { int n; int adj[MAX_VERTICES][MAX_VERTICES]; } Graph;

int parent[MAX_VERTICES]; int rank[MAX_VERTICES];

void make_set(int x) { parent[x] = x; rank[x] = 0; }

int find_set(int x) { if (x != parent[x]) { parent[x] = find_set(parent[x]); } return parent[x]; }

void union_sets(int x, int y) { int root_x = find_set(x); int root_y = find_set(y); if (rank[root_x] > rank[root_y]) { parent[root_y] = root_x; } else if (rank[root_x] < rank[root_y]) { parent[root_x] = root_y; } else { parent[root_y] = root_x; rank[root_x]++; } }

void init_graph(Graph* G, int n) { G->n = n; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { G->adj[i][j] = INFINITY; } } }

void add_edge(Graph* G, int u, int v, int weight) { G->adj[u][v] = weight; G->adj[v][u] = weight; }

void sort_edges(Edge* edges, int m) { for (int i = 0; i < m - 1; i++) { for (int j = i + 1; j < m; j++) { if (edges[i].weight > edges[j].weight) { Edge temp = edges[i]; edges[i] = edges[j]; edges[j] = temp; } } } }

void kruskal(Graph* G, Edge* MST) { int m = 0; Edge edges[MAX_VERTICES * MAX_VERTICES / 2]; for (int u = 0; u < G->n; u++) { for (int v = u + 1; v < G->n; v++) { if (G->adj[u][v] != INFINITY) { edges[m++] = (Edge) {u, v, G->adj[u][v]}; } } } sort_edges(edges, m); for (int i = 0; i < G->n; i++) { make_set(i); } int k = 0; for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; if (find_set(u) != find_set(v)) { union_sets(u, v); MST[k++] = edges[i]; if (k == G->n - 1) { break; } } } }

void break_circle(Graph* G, Edge* MST, int* n) { int visited[MAX_VERTICES] = {0}; for (int i = 0; i < *n; i++) { visited[MST[i].u] = 1; visited[MST[i].v] = 1; } for (int u = 0; u < G->n; u++) { if (!visited[u]) { continue; } for (int v = 0; v < G->n; v++) { if (!visited[v]) { continue; } if (G->adj[u][v] != INFINITY && find_set(u) != find_set(v)) { int max_weight = -1; int max_edge = -1; for (int i = 0; i < *n; i++) { if ((MST[i].u == u && MST[i].v == v) || (MST[i].u == v && MST[i].v == u)) { if (MST[i].weight > max_weight) { max_weight = MST[i].weight; max_edge = i; } break; } } if (G->adj[u][v] < max_weight) { if (max_edge >= 0) { MST[max_edge] = (Edge) {u, v, G->adj[u][v]}; } else { MST[*n] = (Edge) {u, v, G->adj[u][v]}; (*n)++; } } } } } }

int main() { Graph G; init_graph(&G, 6); add_edge(&G, 0, 1, 6); add_edge(&G, 0, 2, 1); add_edge(&G, 0, 3, 5); add_edge(&G, 1, 2, 5); add_edge(&G, 1, 4, 3); add_edge(&G, 2, 3, 5); add_edge(&G, 2, 4, 6); add_edge(&G, 2, 5, 4); add_edge(&G, 3, 5, 2); add_edge(&G, 4, 5, 6); Edge MST[MAX_VERTICES]; kruskal(&G, MST); int n = G.n - 1; break_circle(&G, MST, &n); printf("Minimum Spanning Tree:\n"); for (int i = 0; i < n; i++) { printf("%d %d %d\n", MST[i].u, MST[i].v, MST[i].weight); } return 0; }

该代码先使用Kruskal算法求出原图的最小生成树，然后再遍历原图中所有已经在最小生成树中的节点，找到与其相连的所有节点，如果有一个节点与其不在同一个连通块中，就尝试将它们之间的边加入最小生成树中，如果加入后最小生成树不再是树，就去掉权值最大的边，反复执行这个过程直到没有圈为止。

该代码可以处理权值为负数的边，但是不能处理存在负权回路的情况。如果存在负权回路，该算法会陷入死循环，或者得到一个无限小的最小生成树