C语言破圈法求带权连通图最小生成树代码详解

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

#define MAX_SIZE 100

typedef struct { int u; // 边的起点 int v; // 边的终点 int w; // 边的权值 } Edge;

typedef struct { int parent; // 父节点 int rank; // 秩 } DisjointSet;

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

int find(DisjointSet ds[], int x) { if (ds[x].parent != x) { ds[x].parent = find(ds, ds[x].parent); } return ds[x].parent; }

void union_set(DisjointSet ds[], int x, int y) { int px = find(ds, x); int py = find(ds, y); if (px == py) { return; } if (ds[px].rank < ds[py].rank) { ds[px].parent = py; } else if (ds[px].rank > ds[py].rank) { ds[py].parent = px; } else { ds[py].parent = px; ds[px].rank++; } }

void kruskal(Edge edges[], int n, int m) { DisjointSet ds[MAX_SIZE]; for (int i = 0; i < n; i++) { ds[i].parent = i; ds[i].rank = 0; } int count = 0; for (int i = 0; i < m; i++) { int u = edges[i].u; int v = edges[i].v; if (find(ds, u) != find(ds, v)) { union_set(ds, u, v); count++; } if (count == n - 1) { break; } } }

void break_circle(Edge edges[], int n, int m) { int visited[MAX_SIZE] = {0}; int parent[MAX_SIZE] = {-1}; int max_weight[MAX_SIZE] = {0}; int start = -1; for (int i = 0; i < m; i++) { if (visited[edges[i].u]) { continue; } int u = edges[i].u; int v = edges[i].v; int w = edges[i].w; visited[u] = 1; parent[u] = v; max_weight[u] = w; int j = v; while (j != u && parent[j] != -1) { visited[j] = 1; if (max_weight[j] < w) { max_weight[j] = w; parent[j] = u; } j = parent[j]; } if (j == u) { continue; } start = j; int end = u; int sum_weight = 0; while (end != start) { int w = max_weight[end]; sum_weight += w; end = parent[end]; } sum_weight += max_weight[start]; for (int k = 0; k < m; k++) { if (visited[edges[k].u] && visited[edges[k].v]) { edges[k].w -= sum_weight; } } break_circle(edges, n, m); break; } }

int main() { int n, m; scanf("%d%d", &n, &m); Edge edges[MAX_SIZE]; for (int i = 0; i < m; i++) { scanf("%d%d%d", &edges[i].u, &edges[i].v, &edges[i].w); edges[i].u--; edges[i].v--; } qsort(edges, m, sizeof(Edge), cmp); break_circle(edges, n, m); kruskal(edges, n, m); int sum_weight = 0; for (int i = 0; i < m; i++) { if (find(ds, edges[i].u) != find(ds, edges[i].v)) { union_set(ds, edges[i].u, edges[i].v); sum_weight += edges[i].w; } } printf("%d\n", sum_weight); return 0; }