c语言实现最小生成树代码

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

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

// 定义边结构体
typedef struct {
    int src; // 边的起始节点
    int dest; // 边的目标节点
    int weight; // 边的权值
} Edge;

// 定义图结构体
typedef struct {
    int V; // 图中节点的数量
    int E; // 图中边的数量
    Edge* edges; // 存储边的数组
} Graph;

// 创建图
Graph* createGraph(int V, int E) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->E = E;
    graph->edges = (Edge*)malloc(E * sizeof(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) {
    Edge* edge1 = (Edge*)a;
    Edge* edge2 = (Edge*)b;
    return edge1->weight - edge2->weight;
}

// 使用Kruskal算法求最小生成树
void kruskalMST(Graph* graph) {
    int V = graph->V;
    Edge result[V]; // 存储最小生成树的结果
    int e = 0; // 结果数组的索引
    int i = 0; // 边数组的索引

    qsort(graph->edges, graph->E, sizeof(Edge), compare); // 对边进行排序

    int parent[V];
    for (int v = 0; v < V; v++)
        parent[v] = -1;

    while (e < V - 1 && i < graph->E) {
        Edge nextEdge = graph->edges[i++];

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

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

    printf("最小生成树的边:\n");
    for (i = 0; i < e; i++) {
        printf("%d -- %d, 权值: %d\n", result[i].src, result[i].dest, result[i].weight);
    }
}

int main() {
    int V = 4; // 节点数量
    int E = 5; // 边数量
    Graph* graph = createGraph(V, E);

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

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

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

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

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

    kruskalMST(graph);

    return 0;
}

这段代码实现了Kruskal算法来求解最小生成树。你可以根据具体的需求修改节点数量、边数量以及边的信息。运行代码后，将会输出最小生成树的边及其权值。