Kruskal算法详解（C语言实现最小生成树的完整教程）

Kruskal算法的关键：并查集（Union-Find）

为了高效判断“加入某条边是否会形成环”，我们需要使用一种叫做并查集（Disjoint Set Union, DSU）的数据结构。并查集支持两个操作：

• Find：查找某个节点所属的集合（根节点）
• Union：合并两个集合

通过并查集，我们可以快速判断两个顶点是否已在同一连通分量中——如果在，则加边会成环；如果不在，则可以安全加入。

C语言实现步骤

下面是完整的实现流程：

1. 定义边结构体，包含起点、终点和权重
2. 对所有边按权重升序排序（可用 qsort）
3. 初始化并查集
4. 遍历排序后的边，若两端点不在同一集合，则加入MST，并执行Union操作

完整C语言代码示例

#include <stdio.h>#include <stdlib.h>// 边结构体typedef struct {    int src, dest, weight;} Edge;// 图结构体typedef struct {    int V, E;    Edge* edges;} Graph;// 并查集：查找根节点（带路径压缩）int find(int parent[], int i) {    if (parent[i] == -1)        return i;    return parent[i] = find(parent, parent[i]);}// 并查集：合并两个集合void Union(int parent[], int x, int y) {    parent[x] = y;}// 比较函数，用于qsort排序边int compare(const void* a, const void* b) {    Edge* e1 = (Edge*)a;    Edge* e2 = (Edge*)b;    return e1->weight - e2->weight;}// Kruskal算法主函数void KruskalMST(Graph* graph) {    int V = graph->V;    Edge result[V];    int e = 0; // result数组索引    int i = 0; // edges数组索引    // 步骤1：按权重排序所有边    qsort(graph->edges, graph->E, sizeof(Edge), compare);    // 步骤2：初始化并查集    int parent[V];    for (int v = 0; v < V; ++v)        parent[v] = -1;    // 步骤3：遍历所有边    while (e < V - 1 && i < graph->E) {        Edge next_edge = graph->edges[i++];        int x = find(parent, next_edge.src);        int y = find(parent, next_edge.dest);        // 如果不形成环，则加入MST        if (x != y) {            result[e++] = next_edge;            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 = (Graph*)malloc(sizeof(Graph));    graph->V = V;    graph->E = E;    graph->edges = (Edge*)malloc(graph->E * sizeof(Edge));    // 添加边 (src, dest, weight)    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);    free(graph->edges);    free(graph);    return 0;}

算法复杂度分析

- 时间复杂度：主要由排序决定，为 O(E log E)，其中 E 是边的数量。
- 空间复杂度：O(V)，用于存储并查集，V 是顶点数量。

总结

通过本教程，你已经掌握了Kruskal算法的核心思想、并查集数据结构的应用，以及如何用C语言实现最小生成树。这是图论算法中的基础内容，也是面试和竞赛中的高频考点。建议你动手敲一遍代码，加深理解！

记住，学习图论算法教程的关键在于多练习、多思考。祝你在算法之路上越走越远！