给定一个带权图，求其最小生成树。使用避圈法或破圈法，用c语言编写

以下是使用避圈法（Kruskal算法）求带权图最小生成树的C语言实现：

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

// 定义边的结构体
typedef struct edge {
    int from; // 起点
    int to; // 终点
    int weight; // 权重
} Edge;

// 定义并查集结构体
typedef struct union_find {
    int *parent; // 存放节点的父节点
    int *rank; // 存放节点的秩（树的高度）
} UnionFind;

// 初始化并查集
UnionFind *createUnionFind(int n) {
    UnionFind *uf = (UnionFind *) malloc(sizeof(UnionFind));
    uf->parent = (int *) malloc(n * sizeof(int));
    uf->rank = (int *) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        uf->parent[i] = i; // 初始时每个节点的父节点都是自己
        uf->rank[i] = 0; // 初始时每个节点的秩都是0
    }
    return uf;
}

// 查找节点所在集合的根节点
int find(UnionFind *uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]); // 路径压缩
    }
    return uf->parent[x];
}

// 合并两个集合
void unionSets(UnionFind *uf, int x, int y) {
    int rootX = find(uf, x);
    int rootY = find(uf, y);
    if (rootX != rootY) {
        if (uf->rank[rootX] < uf->rank[rootY]) {
            uf->parent[rootX] = rootY;
        } else if (uf->rank[rootX] > uf->rank[rootY]) {
            uf->parent[rootY] = rootX;
        } else {
            uf->parent[rootY] = rootX;
            uf->rank[rootX]++;
        }
    }
}

// 比较两条边的权重，用于排序
int compare(const void *a, const void *b) {
    Edge *edgeA = (Edge *) a;
    Edge *edgeB = (Edge *) b;
    return edgeA->weight - edgeB->weight;
}

// 使用避圈法（Kruskal算法）求最小生成树
Edge *kruskal(int **graph, int n, int *numEdges) {
    // 构造边的数组
    Edge *edges = (Edge *) malloc(n * n * sizeof(Edge));
    int index = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (graph[i][j] != 0) {
                edges[index].from = i;
                edges[index].to = j;
                edges[index].weight = graph[i][j];
                index++;
            }
        }
    }
    *numEdges = index;

    // 对边按权重进行排序
    qsort(edges, *numEdges, sizeof(Edge), compare);

    // 使用并查集维护连通性
    UnionFind *uf = createUnionFind(n);
    Edge *result = (Edge *) malloc((n - 1) * sizeof(Edge));
    int count = 0;
    for (int i = 0; i < *numEdges; i++) {
        int from = edges[i].from;
        int to = edges[i].to;
        if (find(uf, from) != find(uf, to)) {
            result[count] = edges[i];
            count++;
            unionSets(uf, from, to);
            if (count == n - 1) {
                break;
            }
        }
    }

    // 释放内存
    free(uf->parent);
    free(uf->rank);
    free(uf);
    free(edges);

    return result;
}

int main() {
    int n = 5; // 图的节点数
    int **graph = (int **) malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) {
        graph[i] = (int *) malloc(n * sizeof(int));
    }
    graph[0][1] = 2;
    graph[0][3] = 6;
    graph[1][2] = 3;
    graph[1][3] = 8;
    graph[1][4] = 5;
    graph[2][4] = 7;
    graph[3][4] = 9;

    int numEdges;
    Edge *result = kruskal(graph, n, &numEdges);

    printf("最小生成树的边为：\n");
    for (int i = 0; i < n - 1; i++) {
        printf("(%d, %d, %d)\n", result[i].from, result[i].to, result[i].weight);
    }

    // 释放内存
    for (int i = 0; i < n; i++) {
        free(graph[i]);
    }
    free(graph);
    free(result);

    return 0;
}

上述代码中，我们使用了并查集来维护连通性，并使用边的权重对边进行排序。最终得到的结果是最小生成树的所有边。