C语言实现带权连通图最小生成树的破圈法算法

'破圈法'是求带权连通图最小生成树的一种方法，其思路是任意取一个圈，去掉圈上权值最大的边，反复执行这个步骤，直到图中没有圈为止。

代码实现

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

#define MAXV 1000
#define INF 1000000

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

// 读入边的信息
void read_edge(int n, int m, Edge *edges) {
    int i;
    for (i = 0; i < m; i++) {
        scanf('%d%d%d', &edges[i].u, &edges[i].v, &edges[i].w);
    }
}

// 初始化并查集
void make_set(int *p, int n) {
    int i;
    for (i = 1; i <= n; i++) {
        p[i] = i;
    }
}

// 查找集合代表元
int find_set(int *p, int x) {
    if (p[x] != x) {
        p[x] = find_set(p, p[x]);
    }
    return p[x];
}

// 合并两个集合
void union_set(int *p, int x, int y) {
    int px = find_set(p, x);
    int py = find_set(p, y);
    if (px != py) {
        p[px] = py;
    }
}

// 比较边的权值大小
int cmp_edge(const void *a, const void *b) {
    return ((Edge*)a)->w - ((Edge*)b)->w;
}

// 破圈法求最小生成树
void kruskal(int n, int m, Edge *edges, Edge *result) {
    int i, j, k;
    int *p = (int*)malloc(sizeof(int) * (n + 1));   // 并查集数组
    make_set(p, n);                                 // 初始化并查集
    
    // 对边按权值从小到大排序
    qsort(edges, m, sizeof(Edge), cmp_edge);
    
    // 依次考虑每条边
    for (i = 0, j = 0; i < m && j < n - 1; i++) {
        // 如果边的两个顶点不在同一个集合中，则加入最小生成树中
        if (find_set(p, edges[i].u) != find_set(p, edges[i].v)) {
            result[j++] = edges[i];
            union_set(p, edges[i].u, edges[i].v);
        }
    }
    
    free(p);
}

int main() {
    int n, m;                       // 顶点数和边数
    Edge edges[MAXV * MAXV / 2];    // 边数组
    Edge result[MAXV - 1];          // 最小生成树的边数组
    int i, sum = 0;                 // sum记录最小生成树的权值和
    
    // 读入顶点数和边数
    scanf('%d%d', &n, &m);
    
    // 读入边的信息
    read_edge(n, m, edges);
    
    // 求最小生成树
    kruskal(n, m, edges, result);
    
    // 计算最小生成树的权值和
    for (i = 0; i < n - 1; i++) {
        sum += result[i].w;
    }
    
    // 输出最小生成树的权值和和边的信息
    printf('Minimum cost = %d\n', sum);
    for (i = 0; i < n - 1; i++) {
        printf('(%d, %d, %d)\n', result[i].u, result[i].v, result[i].w);
    }
    
    return 0;
}

代码说明

结构体定义: 使用 Edge 结构体存储边的信息，包括两个顶点 (u, v) 和权值 (w)。
读入边信息: 函数 read_edge 用于读入边的信息，并存储在 edges 数组中。
并查集操作: 代码使用并查集数据结构来判断两个顶点是否在同一个连通分量中，并使用 make_set、find_set 和 union_set 函数进行操作。
排序: 函数 cmp_edge 用于比较边的权值大小，qsort 函数对边数组按照权值从小到大排序。
破圈法: 函数 kruskal 使用破圈法求最小生成树。
结果输出: 代码输出最小生成树的权值和和边的信息。

总结

该代码通过 C 语言实现了破圈法算法，可以用来求解带权连通图的最小生成树。代码结构清晰，并附带详细的注释，方便读者理解和学习。