并查集的时间复杂度经过路径压缩和按秩合并优化后接近o(α(n))，其中α(n)是反阿克曼函数，在实际应用中可视为常数，因此可近似认为是o(1)，未优化时最坏情况为o(n)；其核心优化方法包括路径压缩和按秩合并；主要应用场景有判断图的连通性、kruskal算法中的环检测、动态连通性维护、图像处理中的区域合并以及游戏开发中的阵营判定等问题。
并查集，简单来说，就是用来解决集合合并和查询问题的。它能告诉你两个元素是否属于同一个集合，也能把两个集合合并成一个。
解决方案
并查集的核心是两个操作：
- 查找 (Find): 找到元素所属的集合的代表元素。
- 合并 (Union): 将两个元素所属的集合合并成一个。
下面是JS实现并查集的基本代码：
class UnionFind {
constructor(n) {
this.parent = new Array(n);
this.rank = new Array(n).fill(0); // 用于优化，记录树的高度
for (let i = 0; i < n; i++) {
this.parent[i] = i; // 初始时，每个元素都是一个独立的集合，父节点指向自己
}
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // 路径压缩
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
isConnected(x, y) {
return this.find(x) === this.find(y);
}
}
// 示例
const uf = new UnionFind(10); // 创建一个包含10个元素的并查集
uf.union(0, 1);
uf.union(2, 3);
uf.union(1, 2);
console.log(uf.isConnected(0, 3)); // true
console.log(uf.isConnected(0, 4)); // false并查集的时间复杂度是多少？
未经优化的并查集，
find和
union操作的时间复杂度是 O(n)，n 是元素的总数。这是因为在最坏情况下，
find操作可能需要遍历整个树。
但经过路径压缩和按秩合并优化后，平均时间复杂度接近 O(α(n))，其中 α(n) 是反阿克曼函数，增长非常缓慢，在实际应用中可以认为是一个常数，所以可以近似看作 O(1)。
并查集有哪些优化方法？
主要有两种优化方法：
-
路径压缩 (Path Compression): 在
find
操作中，将访问过的每个节点直接指向根节点。这样下次查找时，路径就大大缩短了。find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // 路径压缩 } return this.parent[x]; } -
按秩合并 (Union by Rank): 在
union
操作中，将高度较低的树连接到高度较高的树上。这样可以尽量保持树的平衡，避免出现极端情况。rank
数组记录了树的高度（或者说是深度的一个上界）。union(x, y) { const rootX = this.find(x); const rootY = this.find(y); if (rootX !== rootY) { if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else if (this.rank[rootX] > this.rank[rootY]) { this.parent[rootY] = rootX; } else { this.parent[rootY] = rootX; this.rank[rootX]++; } } }
并查集在实际开发中有什么应用场景？
并查集在很多场景下都非常有用，比如：
判断图的连通性: 可以用来判断一个图是否是连通的，或者计算图中连通分量的个数。例如，社交网络中判断两个人是否是朋友关系（间接朋友也算）。
Kruskal 算法: 在 Kruskal 算法中，用于判断加入一条边是否会形成环。
动态连通性: 处理动态变化的连通关系。例如，网络连接中，判断两台计算机是否连通，以及在网络发生变化时快速更新连通信息。
图像处理: 在图像分割中，可以将相邻且颜色相似的像素合并成一个区域。
游戏开发: 例如，在一些游戏中，判断两个物体是否属于同一个阵营，或者合并两个相邻的区域。
总而言之，并查集是一种非常实用且高效的数据结构，尤其在处理涉及集合合并和查询的问题时，能发挥很大的作用。理解并掌握它，对于解决实际问题非常有帮助。
