Kruskal算法C语言如何实现并查集优化？

Kruskal算法的C语言实现

Kruskal算法是一种用于寻找无连通图的最小生成树的贪心算法,下面我将提供一个完整的C语言实现，包括并查集数据结构来高效处理边集。

完整代码实现

#include <stdio.h>
#include <stdlib.h>
// 边的结构体
struct Edge {
    int src, dest, weight;
};
// 图的结构体
struct Graph {
    int V, E; // V是顶点数，E是边数
    struct Edge* edge; // 边数组
};
// 并查集的结构体
struct subset {
    int parent;
    int rank;
};
// 创建图
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(struct subset subsets[], int i) {
    if (subsets[i].parent != i)
        subsets[i].parent = find(subsets, subsets[i].parent);
    return subsets[i].parent;
}
// 合并操作（按秩合并）
void Union(struct subset subsets[], int x, int y) {
    int xroot = find(subsets, x);
    int yroot = find(subsets, y);
    if (subsets[xroot].rank < subsets[yroot].rank)
        subsets[xroot].parent = yroot;
    else if (subsets[xroot].rank > subsets[yroot].rank)
        subsets[yroot].parent = xroot;
    else {
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
// 比较函数，用于qsort
int compareEdges(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; // 排序后的边计数器
    // 1. 将所有边按权重非递减顺序排序
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), compareEdges);
    // 分配内存用于创建V个子集
    struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));
    // 初始化每个子集
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    // 遍历所有排序后的边
    while (e < V - 1 && i < graph->E) {
        struct Edge next_edge = graph->edge[i++];
        int x = find(subsets, next_edge.src);
        int y = find(subsets, next_edge.dest);
        // 如果不形成环，则包含这条边
        if (x != y) {
            result[e++] = next_edge;
            Union(subsets, x, y);
        }
    }
    // 打印结果
    printf("Minimum Spanning Tree:\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; // 边数
    struct Graph* graph = createGraph(V, E);
    // 添加边 (src, dest, weight)
    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;
}

算法步骤说明

1. 初始化：将图中所有边按权重从小到大排序。
2. 构建最小生成树：从排序后的边集中依次选择边，如果加入该边不会形成环，则将其加入最小生成树。
3. 检测环：使用并查集数据结构来高效检测加入边是否会形成环。
4. 输出结果：最终输出构成最小生成树的所有边。

时间复杂度分析

• 排序边：O(E log E)
• 并查集操作：每个查找和合并操作接近O(1)（带路径压缩和按秩合并）
• 总体时间复杂度：O(E log E)

注意事项

1. 该实现假设顶点编号从0开始。
2. 如果图中存在多个相同权重的边,输出结果可能不唯一，但最小生成树的权重总和是唯一的。
3. 该算法不适用于有向图。

您可以根据需要修改测试代码中的顶点数、边数和边的具体信息来测试不同的图结构。