用c语言编写一个完整的可运行的代码采用破圈法求一个带权连通图的最小生成树可输入顶点数边数以及权值破圈法是带权连通图求最小生成树的另一种方法其思路是任意取一个圈去掉圈上图中权最大的一个边反复执行这个步骤直到图中没有圈为止通过输入边顶点跟权值确定最小生成树

的过程，输出最小生成树的边与权值之和。

代码如下：

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

#define MAX_VERTEX_NUM 100
#define MAX_EDGE_NUM 1000

typedef struct {
    int from;
    int to;
    int weight;
} Edge;  // 定义边

typedef struct {
    int vertex;
    int parent;
} UnionFind;  // 定义并查集结构体

void swap(Edge* a, Edge* b) {
    Edge temp = *a;
    *a = *b;
    *b = temp;
}

void sort(Edge edgeList[], int edgeNum) {
    for (int i = 0; i < edgeNum - 1; i++) {
        for (int j = i + 1; j < edgeNum; j++) {
            if (edgeList[i].weight > edgeList[j].weight) {
                swap(&edgeList[i], &edgeList[j]);
            }
        }
    }
}

int find(UnionFind ufSet[], int x) {
    int root = x;
    while (ufSet[root].parent >= 0) {
        root = ufSet[root].parent;
    }
    while (x != root) {
        int parent = ufSet[x].parent;
        ufSet[x].parent = root;
        x = parent;
    }
    return root;
}

void merge(UnionFind ufSet[], int x, int y) {
    int root1 = find(ufSet, x);
    int root2 = find(ufSet, y);
    if (ufSet[root1].parent < ufSet[root2].parent) {
        ufSet[root1].parent += ufSet[root2].parent;
        ufSet[root2].parent = root1;
    } else {
        ufSet[root2].parent += ufSet[root1].parent;
        ufSet[root1].parent = root2;
    }
}

void kruskal(Edge edgeList[], int edgeNum, int vertexNum) {
    UnionFind* ufSet = (UnionFind*)malloc(sizeof(UnionFind) * vertexNum);
    for (int i = 0; i < vertexNum; i++) {
        ufSet[i].vertex = i;
        ufSet[i].parent = -1;
    }
    int edgeCount = 0;
    int minWeightSum = 0;
    for (int i = 0; i < edgeNum; i++) {
        int from = edgeList[i].from;
        int to = edgeList[i].to;
        if (find(ufSet, from) != find(ufSet, to)) {
            merge(ufSet, from, to);
            edgeCount++;
            minWeightSum += edgeList[i].weight;
            if (edgeCount == vertexNum - 1) {
                break;
            }
        }
    }
    printf("Minimum weight sum: %d\n", minWeightSum);
    free(ufSet);
}

int main() {
    int vertexNum, edgeNum;
    printf("Please enter the number of vertices and edges: ");
    scanf("%d %d", &vertexNum, &edgeNum);
    Edge* edgeList = (Edge*)malloc(sizeof(Edge) * edgeNum);
    printf("Please enter the edges and weights:\n");
    for (int i = 0; i < edgeNum; i++) {
        scanf("%d %d %d", &edgeList[i].from, &edgeList[i].to, &edgeList[i].weight);
    }
    sort(edgeList, edgeNum);
    kruskal(edgeList, edgeNum, vertexNum);
    free(edgeList);
    return 0;
}
``