使用路径压缩是为了降低树的高度，使find操作的均摊时间复杂度接近o(α(n))，从而显著提升查询效率；1. 路径压缩在每次find时将路径上所有节点直接连到根节点，减少后续查找时间；2. 基于rank的合并策略通过将低rank树合并到高rank树上，防止树过深；3. 当rank相同时合并后需将新根的rank加1；4. 并查集适用于图的连通性判断、kruskal算法、网络连接、图像处理和社交网络等场景。
并查集是一种用于处理集合合并和查询问题的高效数据结构。它能快速判断两个元素是否属于同一集合，以及将两个集合合并成一个。Java实现并查集，重点在于
find（查找根节点）和
union（合并集合）这两个核心操作，而路径压缩则是一种优化手段，能显著提升查找效率。
public class UnionFind {
private int[] parent;
private int[] rank; // 用于优化合并，记录树的高度
public UnionFind(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]); // 路径压缩：将x的父节点直接指向根节点
}
return parent[x];
}
// 合并两个集合，基于rank的优化
public void union(int x, int y) {
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY) {
// 将rank低的树合并到rank高的树上
if (rank[rootX] < rank[rootY]) {
parent[rootX] = rootY;
} else if (rank[rootX] > rank[rootY]) {
parent[rootY] = rootX;
} else {
// 如果rank相同，则随便合并，并增加rank
parent[rootY] = rootX;
rank[rootX]++;
}
}
}
// 判断两个元素是否在同一个集合中
public boolean isConnected(int x, int y) {
return find(x) == find(y);
}
public static void main(String[] args) {
UnionFind uf = new UnionFind(10);
uf.union(1, 2);
uf.union(2, 3);
uf.union(4, 5);
uf.union(6, 7);
uf.union(5, 6);
uf.union(3, 7);
System.out.println("1 and 5 are connected: " + uf.isConnected(1, 5)); // true
System.out.println("4 and 8 are connected: " + uf.isConnected(4, 8)); // false
}
}为什么要使用路径压缩优化并查集？
路径压缩是并查集优化中的关键一步。没有路径压缩，
find操作可能需要遍历整个树的高度才能找到根节点，时间复杂度接近O(n)，其中n是树的高度。有了路径压缩，每次
find操作都会将访问路径上的所有节点直接连接到根节点，大大降低了树的高度，使得后续的
find操作更加高效。理论上，经过路径压缩优化后，并查集的均摊时间复杂度接近O(α(n))，其中α(n)是反阿克曼函数，增长极其缓慢，可以认为是一个常数。
如何选择合适的rank合并策略？
在
union操作中，基于rank的合并策略能避免树的深度增长过快。rank可以简单理解为树的高度（实际上是树的深度的上界，因为路径压缩会改变树的实际结构）。总是将rank较低的树合并到rank较高的树上，可以有效地控制树的高度，从而降低
find操作的时间复杂度。如果两个树的rank相同，则随便合并，并将合并后的树的rank加1。 这种策略保证了树的深度增长是缓慢的，从而保证了并查集的高效性。
立即学习“Java免费学习笔记（深入）”；
并查集在实际项目中有哪些应用场景？
并查集在很多场景下都有应用，比如：
- 判断图的连通性： 可以使用并查集来判断一个无向图是否连通，或者计算连通分量的个数。
- 最小生成树算法： Kruskal算法是求解最小生成树的经典算法，其中就用到了并查集来判断两个节点是否属于同一个连通分量，避免形成环路。
- 网络连接： 可以用并查集来模拟网络连接，判断两台计算机是否可以直接或间接连接。
- 图像处理： 在图像分割、区域标记等任务中，可以使用并查集来合并相邻的相似区域。
- 社交网络： 可以用来发现社交网络中的社群结构。
总而言之，并查集是一种非常实用的数据结构，掌握它可以解决很多实际问题。理解其原理和优化策略，能帮助你更好地应用它。
