C语言实现并查集：原理、实践与优化

简介

并查集（Union-Find Set）是一种非常实用的数据结构，用于处理不相交集合的合并与查询问题。在许多算法和实际应用中，比如图的连通性判断、最小生成树算法等，都能看到并查集的身影。本文将深入探讨如何使用C语言实现并查集，从基础概念开始，逐步介绍其使用方法、常见实践以及最佳实践。

目录

1. 基础概念
2. 使用方法
   • 初始化
   • 查找操作
   • 合并操作
3. 常见实践
   • 解决连通性问题
   • 实现Kruskal算法
4. 最佳实践
   • 路径压缩优化
   • 按秩合并优化
5. 代码示例
6. 小结
7. 参考资料

基础概念

并查集本质上是一种树形数据结构，每个集合以一棵树的形式表示。树中的每个节点代表集合中的一个元素，树根作为集合的代表。在并查集中，有两个核心操作：

• 查找（Find）：确定元素所属的集合，即找到该元素所在树的根节点。
• 合并（Union）：将两个不同的集合合并成一个集合，通常是将一棵较小的树连接到另一棵较大的树的根节点上。

使用方法

初始化

在使用并查集之前，需要对其进行初始化。我们可以使用一个数组 parent 来存储每个元素的父节点。初始时，每个元素的父节点就是它自身，即每个元素单独构成一个集合。

#define MAXN 1000

int parent[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
    }
}

查找操作

查找操作是找到给定元素所在集合的代表（根节点）。通过不断向上追溯父节点，直到找到根节点（即父节点是自身的节点）。

int find(int x) {
    while (x!= parent[x]) {
        x = parent[x];
    }
    return x;
}

合并操作

合并操作将两个不同的集合合并成一个集合。首先找到两个元素所在集合的根节点，然后将其中一个根节点的父节点设置为另一个根节点。

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX!= rootY) {
        parent[rootX] = rootY;
    }
}

常见实践

解决连通性问题

在图论中，判断两个节点是否连通是一个常见问题。可以使用并查集来高效解决。例如，对于一个无向图，每次加入一条边时，将边的两个端点所在的集合合并。查询两个节点是否连通时，只需判断它们是否属于同一个集合。

// 假设有一个图，通过边的数组表示
typedef struct {
    int u, v;
} Edge;

// 判断图中两个节点是否连通
int isConnected(int u, int v) {
    return find(u) == find(v);
}

// 示例用法
int main() {
    int n = 5; // 节点数
    init(n);

    Edge edges[] = {{0, 1}, {2, 3}, {1, 2}};
    int m = sizeof(edges) / sizeof(edges[0]);

    for (int i = 0; i < m; i++) {
        unionSets(edges[i].u, edges[i].v);
    }

    if (isConnected(0, 3)) {
        printf("节点 0 和 3 是连通的\n");
    } else {
        printf("节点 0 和 3 不连通\n");
    }

    return 0;
}

实现Kruskal算法

Kruskal算法是用于计算最小生成树的贪心算法。在算法过程中，需要不断判断边的两个端点是否在同一个集合中，以避免形成环。并查集可以很好地满足这个需求。

// 边的结构体，增加权重属性
typedef struct {
    int u, v, w;
} Edge;

// 比较函数，用于qsort对边按权重排序
int compareEdges(const void* a, const void* b) {
    Edge* edgeA = (Edge*)a;
    Edge* edgeB = (Edge*)b;
    return edgeA->w - edgeB->w;
}

// 计算最小生成树的权重
int kruskalMST(int n, Edge edges[], int m) {
    init(n);
    qsort(edges, m, sizeof(Edge), compareEdges);

    int mstWeight = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i].u;
        int v = edges[i].v;
        int w = edges[i].w;

        if (find(u)!= find(v)) {
            unionSets(u, v);
            mstWeight += w;
        }
    }

    return mstWeight;
}

// 示例用法
int main() {
    int n = 4; // 节点数
    int m = 5; // 边数
    Edge edges[] = {{0, 1, 10}, {0, 2, 6}, {0, 3, 5}, {1, 3, 15}, {2, 3, 4}};

    int mstWeight = kruskalMST(n, edges, m);
    printf("最小生成树的权重是: %d\n", mstWeight);

    return 0;
}

最佳实践

路径压缩优化

在查找操作中，路径压缩可以显著提高并查集的性能。在找到根节点后，将查找路径上的所有节点直接连接到根节点，这样下次查找时可以更快地找到根节点。

int find(int x) {
    if (x!= parent[x]) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

按秩合并优化

按秩合并是另一种优化策略。我们为每个集合维护一个秩（可以理解为树的高度），在合并时，将秩较小的树连接到秩较大的树的根节点上，这样可以保证树的高度增长较慢，从而提高查找效率。

int rank[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX!= rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
            rank[rootY]++;
        }
    }
}

代码示例

下面是一个完整的C语言实现并查集的代码示例，包含初始化、查找、合并操作以及路径压缩和按秩合并的优化：

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

#define MAXN 1000

int parent[MAXN];
int rank[MAXN];

void init(int n) {
    for (int i = 0; i < n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }
}

int find(int x) {
    if (x!= parent[x]) {
        parent[x] = find(parent[x]); // 路径压缩
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX!= rootY) {
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootX] = rootY;
            rank[rootY]++;
        }
    }
}

// 判断图中两个节点是否连通
int isConnected(int u, int v) {
    return find(u) == find(v);
}

// 示例用法
int main() {
    int n = 5; // 节点数
    init(n);

    int edges[][2] = {{0, 1}, {2, 3}, {1, 2}};
    int m = sizeof(edges) / sizeof(edges[0]);

    for (int i = 0; i < m; i++) {
        unionSets(edges[i][0], edges[i][1]);
    }

    if (isConnected(0, 3)) {
        printf("节点 0 和 3 是连通的\n");
    } else {
        printf("节点 0 和 3 不连通\n");
    }

    return 0;
}

小结

并查集是一种强大的数据结构，在处理集合合并与查询问题时具有高效性。通过本文，我们学习了并查集的基础概念、使用方法，以及在解决连通性问题和实现Kruskal算法等方面的常见实践。同时，我们还介绍了路径压缩和按秩合并等优化策略，这些策略可以显著提高并查集的性能。希望读者通过本文的学习，能够深入理解并熟练使用C语言实现并查集，在实际编程中灵活运用这一数据结构解决问题。

参考资料

• 《算法导论》（Introduction to Algorithms）
• 《数据结构与算法分析：C语言描述》（Data Structures and Algorithm Analysis in C）
• 各大在线算法学习平台，如LeetCode、HackerRank等。