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

Kruskal 算法是一种用于寻找无向加权图的最小生成树的贪心算法，其核心思想是：按边的权重从小到大依次选择，如果加入该边后不会形成环，则将其加入生成树中，直到所有顶点都被连接。

为了实现这个算法,我们需要解决两个关键问题：

1. 如何高效地选择权重最小的边？ -> 使用优先队列，通常用排序数组来模拟。
2. 如何快速判断加入一条边是否会形成环？ -> 使用并查集数据结构。

下面是完整的 C 语言实现,包含详细的注释和解释。

第一步：理解数据结构

1. 图 的表示：

   • 我们使用邻接矩阵来存储图。graph[V][V] 是一个二维数组，graph[i][j] 存储顶点 i 和 j 之间的边的权重。i 和 j 之间没有边，则值为 0。
   • V 是顶点的数量。

2. 边 的表示：

   
   （图片来源网络，侵删）
   • 我们需要一个结构体来表示一条边。

     struct Edge {
     int src;      // 边的起点
     int dest;     // 边的终点
     int weight;   // 边的权重
     };

3. 并查集：

   • 这是一个用于管理不相交集合的数据结构，非常适合处理“合并”和“查找”操作。
   • find(int parent[], int i): 查找元素 i 所在的集合的根节点（代表元）。
   • union(int parent[], int rank[], int x, int y): 合并两个元素 x 和 y 所在的集合，为了优化，我们使用路径压缩和按秩合并。

第二步：算法实现步骤

1. 创建边集：遍历邻接矩阵,将所有非零权重的边存入一个边数组中。
2. 排序边集：根据边的权重,对所有边进行升序排序。
3. 初始化并查集：为每个顶点创建一个独立的集合,即每个顶点都是自己的父节点。
4. 构建 MST：
   • 从排序后的边数组中,按顺序取出每一条边。
   • 使用 find 操作查找这条边的两个顶点 src 和 dest 是否属于同一个集合。
   • 如果不属于同一个集合（即不会形成环），则：
     • 将这条边加入 MST。
     • 使用 union 操作将这两个顶点所在的集合合并。
   • 如果属于同一个集合（会形成环）,则跳过这条边。
   • 重复此过程，直到 MST 中包含 V-1 条边（对于 V 个顶点的图，MST 有 V-1 条边）或所有边都处理完毕。

第三步：完整的 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) {
    // 找到元素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 {
        // 如果秩相同，则任意连接，并且秩加1
        subsets[yroot].parent = xroot;
        subsets[xroot].rank++;
    }
}
// 比较函数，用于qsort排序边
int myComp(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; // result数组的索引
    int i = 0; // 排序后的边数组的索引
    // 1. 将所有边按权重从小到大排序
    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
    // 为并查集分配内存
    struct subset* subsets = (struct subset*)malloc(V * sizeof(struct subset));
    // 2. 初始化并查集，每个顶点是一个独立的集合
    for (int v = 0; v < V; ++v) {
        subsets[v].parent = v;
        subsets[v].rank = 0;
    }
    // 3. 遍历排序后的所有边
    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);
        // 如果x和y不在同一个集合，则不会形成环
        if (x != y) {
            result[e++] = next_edge; // 将此边加入MST
            Union(subsets, x, y);    // 合并这两个集合
        }
        // 如果x和y在同一个集合，则跳过这条边（会形成环）
    }
    // 4. 打印最终的最小生成树
    printf("以下是构成最小生成树的边:\n");
    int minimumCost = 0;
    for (i = 0; i < e; ++i) {
        printf("%d -- %d == %d\n", result[i].src, result[i].dest, result[i].weight);
        minimumCost += result[i].weight;
    }
    printf("\n最小生成树的总权重为: %d\n", minimumCost);
}
// 主函数，用于测试
int main() {
    /* 创建如下所示的图
          10
       0--------1
       |  \     |
      6|   5\   |15
       |     \  |
       2--------3
          4
    */
    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;
    // 运行Kruskal算法
    KruskalMST(graph);
    return 0;
}

代码解释

1. createGraph: 动态分配内存,创建一个图对象。
2. find: 这是并查集的核心。if (subsets[i].parent != i) 递归地向上查找根节点。subsets[i].parent = find(...) 这一行是路径压缩，它会在查找路径上将所有节点直接指向根节点,从而加速后续的查找操作。
3. Union: 这是并查集的另一个核心，它通过比较两个根节点的 rank（秩，可以理解为树的高度）来决定如何合并，将秩较小的树连接到秩较大的树下，可以保持树的平衡，确保 find 操作的效率，如果秩相同,则合并后秩加一。
4. myComp: 这是 qsort 函数需要的比较函数，用于对边数组进行排序，它告诉 qsort 应该根据 weight 字段来排序。
5. KruskalMST:
   • qsort(graph->edge, ...): 对所有边进行排序。
   • struct subset* subsets = ...: 为并查集分配内存。
   • for (int v = 0; v < V; ++v): 初始化并查集，每个顶点初始时都是自己的父节点,秩为0。
   • while (e < V - 1 && i < graph->E): 循环直到找到足够的边构成MST（V-1条）或者所有边都检查完毕。
   • find(subsets, next_edge.src) 和 find(subsets, next_edge.dest): 查找当前边的两个顶点所属的集合。
   • if (x != y): 如果两个顶点不在同一个集合，说明加入这条边不会形成环。
     • result[e++] = next_edge;: 将这条边加入结果集。
     • Union(subsets, x, y);: 合并这两个集合。
   • 遍历 result 数组,打印出MST的边和总权重。

复杂度分析

• 时间复杂度:

  • 排序边：O(E log E)，E 是边的数量。
  • 遍历边和执行并查集操作：O(E * α(V))， 是阿克曼函数的反函数，对于所有实际应用来说，α(V) 可以认为是小于等于4的常数。
  • 总的时间复杂度主要由排序步骤决定，为 O(E log E)，对于稀疏图（E 远小于 V^2），这比 Prim 算法（使用邻接矩阵时为 O(V^2)）更高效。

• 空间复杂度:

  • 存储图：O(V^2) (如果使用邻接矩阵) 或 O(V + E) (如果使用邻接表)。
  • 存储边数组：O(E)。
  • 并查集：O(V)。
  • 结果集：O(V)。
  • 总空间复杂度为 O(V^2 + E)。

这个 C 语言实现清晰地展示了 Kruskal 算法的逻辑,并利用并查集高效地解决了环检测问题。