c语言避圈发求最小生成树

C语言中可以使用Kruskal算法来求解带权连通无向图的最小生成树。Kruskal算法是一种贪心算法，它通过不断选择权重最小的边，并且保证不形成环，直到生成树中包含了所有的顶点为止。

以下是使用C语言实现Kruskal算法求解最小生成树的示例代码：

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

// 定义边的结构体
struct Edge {
    int src, dest, weight;
};

// 定义图的结构体
struct Graph {
    int V, E;
    struct Edge* edge;
};

// 创建图的函数
struct Graph* createGraph(int V, int E) {
    struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
    graph->V = V;
    graph->E = E;
    graph->edge = (struct Edge*)malloc(E * sizeof(struct Edge));
    return graph;
}

// 查找函数，用于查找顶点的父节点
int find(int parent[], int i) {
    if (parent[i] == -1)
        return i;
    return find(parent, parent[i]);
}

// 合并函数，用于合并两个顶点所在的集合
void Union(int parent[], int x, int y) {
    int xset = find(parent, x);
    int yset = find(parent, y);
    parent[xset] = yset;
}

// 比较函数，用于对边按照权重进行排序
int compare(const void* a, const void* b) {
    struct Edge* a1 = (struct Edge*)a;
    struct Edge* b1 = (struct Edge*)b;
    return a1->weight - b1->weight;
}

// Kruskal算法求解最小生成树
void KruskalMST(struct Graph* graph) {
    int V = graph->V;
    struct Edge result[V];
    int e = 0;
    int i = 0;

    // 对边按照权重进行排序
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compare);

    // 创建用于判断是否形成环的数组
    int* parent = (int*)malloc(V * sizeof(int));
    for (int v = 0; v < V; v++)
        parent[v] = -1;

    // 选择权重最小的边，并且保证不形成环
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];

        int x = find(parent, next_edge.src);
        int y = find(parent, next_edge.dest);

        if (x != y) {
            result[e++] = next_edge;
            Union(parent, x, y);
        }
    }

    // 输出最小生成树的边
    printf("Minimum Spanning Tree:\n");
    for (i = 0; i < e; i++) {
        printf("%d -- %d\tWeight: %d\n", result[i].src, result[i].dest, result[i].weight);
    }
}

int main() {
    int V = 4; // 图的顶点数
    int E = 5; // 图的边数
    struct Graph* graph = createGraph(V, E);

    // 添加边的信息
    graph->edge[0].src = 0;
    graph->edge[0].dest = 1;
    graph->edge[0].weight = 10;

    graph->edge[1].src = 0;
    graph->edge[1].dest = 2;
    graph->edge[1].weight = 6;

    graph->edge[2].src = 0;
    graph->edge[2].dest = 3;
    graph->edge[2].weight = 5;

    graph->edge[3].src = 1;
    graph->edge[3].dest = 3;
    graph->edge[3].weight = 15;

    graph->edge[4].src = 2;
    graph->edge[4].dest = 3;
    graph->edge[4].weight = 4;

    KruskalMST(graph);

    return 0;
}

运行以上代码，可以得到带权连通无向图的最小生成树的边的信息。