并查集（Disjoint Set），又称并查集数据结构或不相交集合数据结构，是一种用于处理不相交集合（即各集合之间没有交集）的数据结构。并查集主要支持两种操作：合并（Union）和查找（Find），它在许多算法中扮演着关键角色，特别是在图论中的连通性问题、网络连接问题等方面。
基本概念
并查集通过一棵棵树来表示集合，每棵树代表一个集合，树中的每个节点指向其父节点，根节点指向自身。每个元素都有一个与之对应的节点，这些节点通过指针连接形成树形结构。合并操作将两个不同集合合并为一个集合，而查找操作则查找元素所属的集合，即找到该元素所在树的根节点。
并查集的两大优化策略
为了提高并查集操作的效率，通常会采用两种优化策略：路径压缩（Path Compression）和按秩合并（Union by Rank）。
1. **路径压缩**：路径压缩是在执行查找操作时，通过改变树结构减少树的高度，使得后续查找操作更加高效。在执行查找操作时，将被访问到的节点直接连接到根节点上。这样做的结果是树的高度显著降低。
2. **按秩合并**：按秩合并是在执行合并操作时，将秩（即树的高度或者近似高度）较小的树合并到秩较大的树上，以防止树的高度过大。具体来说，当合并两个集合时，总是将秩较小的树的根指向秩较大的树的根。
这些优化策略使得并查集的时间复杂度接近于常数时间，具体为O(α(n))，其中α是反阿克曼函数，增长极其缓慢，可以认为在实际应用中几乎是常数时间。
并查集的操作
假设我们有一个大小为N的并查集，我们的目标是提供高效的合并和查找操作。以下是并查集的主要操作及其实现：
1. **初始化（MakeSet）**：将每个元素初始化为一个集合，即每个元素作为一个独立的树。
2. **查找（Find）**：查找元素所属的集合，返回该集合的代表元，即树的根节点。
3. **合并（Union）**：将两个不同的集合合并为一个集合。
并查集的实现
下面是基于数组实现的并查集的Java代码示例：
```java class DisjointSet { private int[] parent; private int[] rank; public DisjointSet(int size) { parent = new int[size]; rank = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; // 每个元素的父节点初始化为自己 rank[i] = 0; // 初始秩都为0 } } // 查找操作，带路径压缩 public int find(int x) { if (parent[x] != x) { parent[x] = find(parent[x]); // 路径压缩 } return parent[x]; } // 合并操作，带按秩合并 public void union(int x, int y) { int rootX = find(x); int rootY = find(y); if (rootX == rootY) { return; } if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; } } } ```
使用示例
假设我们有一组元素 {0, 1, 2, 3, 4}，开始时它们各自属于不同的集合。接下来，我们执行以下操作：
1. 执行 `union(0, 1)`，将元素0和元素1所在的集合合并。
2. 执行 `union(2, 3)`，将元素2和元素3所在的集合合并。
3. 执行 `union(1, 3)`，将元素1和元素3所在的集合合并。
最终，元素0、1、2、3将属于同一个集合，而元素4仍然是一个独立的集合。
应用场景
并查集在许多场景中都有广泛应用：
1. **图的连通性判断**：判断图中的两个节点是否连通。
2. **最小生成树**：Kruskal算法利用并查集来检测环。
3. **动态连通性问题**：如网络连接问题，社交网络中的朋友关系等。
总结
并查集是一种高效的数据结构，通过路径压缩和按秩合并等优化方法，可以在接近常数时间内完成查找和合并操作。它在解决图论中的连通性问题、动态连通性问题等方面具有重要作用。掌握并查集对于算法设计和复杂问题的求解非常有帮助。
