克鲁斯卡尔最小生成树C语言代码

克鲁斯卡尔算法是一种用于寻找图中最短路径的算法，但它实际上可以应用到求解最小生成树的问题上。在最简版本中，它是通过贪心策略逐步添加边来构建一棵树，使得所有顶点都包含其中，且边的总权重最小。

下面是一个简单的克鲁斯卡尔算法实现的C语言代码示例，它假设输入的是无向加权邻接表表示的图：

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

typedef struct Edge {
    int src, dest, weight;
} Edge;

typedef struct Graph {
    int V;        // 图中的顶点数
    Edge* edges;  // 边的数组
    int E;        // 边的数量
} Graph;

Graph* create_graph(int V, Edge* edges, int E) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    graph->V = V;
    graph->edges = edges;
    graph->E = E;
    return graph;
}

// Kruskal's Algorithm
void kruskal_mst(Graph* graph) {
    int i, j, min_edge, result[E];
    for (i = 0; i < E; i++) {
        min_edge = i;
    }

    // 将边按权重升序排序
    for (i = 0; i < E; i++) {
        if (graph->edges[min_edge].weight < graph->edges[i].weight) {
            min_edge = i;
        }
    }

    int count = 0;
    for (i = 0; i < E; i++) {
        if (count == graph->V - 1) break; // 找到生成树所需的边
        if (find_set(graph->edges[min_edge].src, graph->edges[min_edge].dest, result)) { // 如果边不形成环
            union_set(graph->edges[min_edge].src, graph->edges[min_edge].dest, result);
            printf("Edge between %d and %d with weight %d\n", graph->edges[min_edge].src, graph->edges[min_edge].dest, graph->edges[min_edge].weight);
            count++;
        }
        min_edge = i;
    }
}

// 查找集合的根节点
int find_set(int v, int parent[], int size[]) {
    if (v == parent[v]) return v;
    return parent[v] = find_set(parent[v], parent, size);
}

// 合并两个集合
void union_set(int a, int b, int parent[], int size[]) {
    a = find_set(a, parent, size);
    b = find_set(b, parent, size);

    if (a != b) {
        if (size[a] > size[b]) {
            parent[b] = a;
            size[a] += size[b];
        } else {
            parent[a] = b;
            size[b] += size[a];
        }
    }
}

// 示例使用
int main() {
    int V = 5; // 顶点数
    Edge edges[] = {{0, 1, 10}, {0, 4, 6}, {1, 2, 8}, {2, 3, 7}, {3, 4, 9}};
    int E = sizeof(edges) / sizeof(edges[0]);

    Graph* graph = create_graph(V, edges, E);
    kruskal_mst(graph);
    free(graph);
    return 0;
}

这个程序首先创建了一个图结构，然后使用Kruskal算法找到最小生成树，并打印出每条边及其连接的顶点。注意这只是一个基础示例，实际应用中可能需要处理更复杂的数据结构和错误检查。