并查集【算法 12】

并查集 (Union-Find) 的基础概念与实现

请添加图片描述

并查集（Union-Find）是一种用于处理不相交集合（disjoint sets）的数据结构，常用于解决连通性问题。典型的应用场景包括动态连通性问题（如网络节点连通性检测）、图论中的最小生成树（Kruskal 算法）、社交网络中的群体归属等。

并查集的两大基本操作

合并操作 (Union): 将两个不同的集合合并为一个集合。
查找操作 (Find): 查询某个元素属于哪个集合，通常通过找到该元素所在集合的代表元（根节点）来实现。

并查集的特点

并查集的核心思想是将集合通过树状结构来表示，每个集合有一个根节点，查找某个元素时可以通过追溯其父节点直到找到根节点。合并操作则是将一个集合的根节点连接到另一个集合的根节点。

基础实现

我们可以通过两个数组来实现并查集：

parent[] 数组：记录每个元素的父节点。
rank[] 数组：记录集合的深度（或称为树的秩）。

#include <stdio.h>#define MAX 1000  // 假设最大元素数为 1000int parent[MAX];
int rank[MAX];// 初始化操作，每个元素自成一个集合
void initialize(int n) {for (int i = 0; i < n; i++) {parent[i] = i;  // 每个元素的父节点都是自己rank[i] = 0;    // 初始时每个集合的秩为 0}
}// 查找操作：查找元素 x 的根节点，并进行路径压缩
int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);  // 递归查找根节点，并进行路径压缩}return parent[x];
}// 合并操作：将两个集合合并，按秩优化
void union_sets(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {// 按秩合并：将秩小的树挂在秩大的树上if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}
}

路径压缩与按秩合并

路径压缩 (Path Compression): 在 find() 操作中，通过递归将查找路径上所有节点直接连接到根节点。这样可以大大减少树的高度，使后续查找更高效。
按秩合并 (Union by Rank): 在合并时，将秩小的树挂到秩大的树上，以减少树的高度，避免退化为链表结构。

时间复杂度分析

并查集的时间复杂度非常接近于常数级别。虽然每次 find 和 union 的复杂度不是固定的常数，但由于路径压缩和按秩合并的优化，其均摊时间复杂度为 O(α(n))，其中 α(n) 为阿克曼函数的反函数，在实际应用中增长极为缓慢，因此可以视为常数时间。

经典应用：Kruskal 最小生成树算法

Kruskal 算法用于构建无向图的最小生成树，它的核心思想是贪心地选择最小权重的边，前提是该边连接的两个顶点不在同一个集合中，这正好可以用并查集来解决。

示例代码：Kruskal 算法

#include <stdio.h>#define MAX 1000typedef struct {int u, v, weight;
} Edge;Edge edges[MAX];
int parent[MAX];
int rank[MAX];
int n, m;  // n 为节点数，m 为边数void initialize() {for (int i = 0; i < n; i++) {parent[i] = i;rank[i] = 0;}
}int find(int x) {if (parent[x] != x) {parent[x] = find(parent[x]);}return parent[x];
}void union_sets(int x, int y) {int rootX = find(x);int rootY = find(y);if (rootX != rootY) {if (rank[rootX] > rank[rootY]) {parent[rootY] = rootX;} else if (rank[rootX] < rank[rootY]) {parent[rootX] = rootY;} else {parent[rootY] = rootX;rank[rootX]++;}}
}int kruskal() {int totalWeight = 0;int edgeCount = 0;initialize();// 假设 edges[] 按权重从小到大排序for (int i = 0; i < m && edgeCount < n - 1; i++) {int u = edges[i].u;int v = edges[i].v;int weight = edges[i].weight;if (find(u) != find(v)) {union_sets(u, v);totalWeight += weight;edgeCount++;}}return totalWeight;
}