用C语言写一个给定一个带权图，用避圈法求其最小生成树的程序

好的，以下是给定一个带权图，用避圈法求其最小生成树的C语言程序：

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

#define MAX_VERTEX_NUM 100 // 图中最多顶点个数
#define INF 65535 // 用于表示正无穷大

// 边的数据结构
typedef struct {
    int u, v; // 两个端点的下标
    int weight; // 权重
} Edge;

// 图的数据结构
typedef struct {
    int vertex[MAX_VERTEX_NUM]; // 顶点数组
    int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
    int vertex_num, edge_num; // 顶点个数和边数
} Graph;

// 初始化图
void init(Graph *G) {
    int i, j;
    for (i = 0; i < G->vertex_num; i++) {
        for (j = 0; j < G->vertex_num; j++) {
            G->edge[i][j] = INF; // 初始化为正无穷大
        }
    }
}

// 读入图的数据
void read_graph(Graph *G) {
    int i, j;
    printf("请输入顶点个数和边数：");
    scanf("%d%d", &G->vertex_num, &G->edge_num);
    printf("请输入顶点的编号：");
    for (i = 0; i < G->vertex_num; i++) {
        scanf("%d", &G->vertex[i]);
    }
    init(G); // 初始化图
    printf("请输入边的信息（起点、终点、权重）：\n");
    for (i = 0; i < G->edge_num; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        G->edge[u][v] = G->edge[v][u] = w; // 无向图，所以要存储两次
    }
}

// 避圈法求最小生成树
void kruskal(Graph *G, Edge *result) {
    int i, j, k = 0;
    int parent[MAX_VERTEX_NUM]; // 记录顶点的父亲
    for (i = 0; i < G->vertex_num; i++) {
        parent[i] = -1; // 初始时所有顶点都没有父亲
    }
    Edge edges[MAX_VERTEX_NUM * MAX_VERTEX_NUM]; // 存储所有边的数组
    for (i = 0; i < G->vertex_num; i++) {
        for (j = i + 1; j < G->vertex_num; j++) {
            if (G->edge[i][j] < INF) { // 如果有边，则存储到数组中
                edges[k].u = i;
                edges[k].v = j;
                edges[k].weight = G->edge[i][j];
                k++;
            }
        }
    }
    // 对所有边按权值从小到大排序
    for (i = 0; i < k - 1; i++) {
        for (j = i + 1; j < k; j++) {
            if (edges[i].weight > edges[j].weight) {
                Edge temp = edges[i];
                edges[i] = edges[j];
                edges[j] = temp;
            }
        }
    }
    // 逐个加入边，直到形成树
    for (i = 0; i < k; i++) {
        int u = edges[i].u, v = edges[i].v;
        while (parent[u] != -1) {
            u = parent[u];
        }
        while (parent[v] != -1) {
            v = parent[v];
        }
        if (u != v) { // 如果不在同一棵树上，则加入该边
            parent[u] = v;
            result[i] = edges[i];
        }
    }
}

// 输出最小生成树
void print_result(Graph *G, Edge *result) {
    int i;
    printf("最小生成树的边为：\n");
    for (i = 0; i < G->vertex_num - 1; i++) {
        printf("(%d, %d) %d\n", G->vertex[result[i].u], G->vertex[result[i].v], result[i].weight);
    }
}

int main() {
    Graph G;
    Edge result[MAX_VERTEX_NUM];
    read_graph(&G);
    kruskal(&G, result);
    print_result(&G, result);
    return 0;
}

以上程序使用了避圈法来求解最小生成树，时间复杂度为$O(eloge)$，其中$e$为边数，$log$为排序的时间复杂度。