当前位置：首页 > 文章列表 > 文章 > 前端 > JS实现并查集及优化技巧

JS实现并查集及优化技巧

2025-08-12 22:39:58 0浏览收藏

本文深入探讨了使用 JavaScript 实现并查集（Union Find）数据结构及其优化方法。并查集主要用于解决集合的合并与查询问题，例如判断元素是否属于同一集合，或将两个集合合并。文章详细讲解了并查集的核心操作：查找（Find）和合并（Union），并提供了 JavaScript 代码示例。针对并查集的时间复杂度问题，重点介绍了路径压缩和按秩合并两种优化策略，优化后的时间复杂度近乎 O(1)。此外，文章还列举了并查集在实际开发中的多种应用场景，包括图的连通性判断、Kruskal 算法中的环检测、动态连通性维护、图像处理以及游戏开发等，旨在帮助开发者更好地理解和运用这一高效的数据结构。

并查集的时间复杂度经过路径压缩和按秩合并优化后接近O(α(n))，其中α(n)是反阿克曼函数，在实际应用中可视为常数，因此可近似认为是O(1)，未优化时最坏情况为O(n)；其核心优化方法包括路径压缩和按秩合并；主要应用场景有判断图的连通性、Kruskal算法中的环检测、动态连通性维护、图像处理中的区域合并以及游戏开发中的阵营判定等问题。

JS如何实现并查集？并查集的优化

并查集，简单来说，就是用来解决集合合并和查询问题的。它能告诉你两个元素是否属于同一个集合，也能把两个集合合并成一个。

解决方案

并查集的核心是两个操作：

查找 (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]++;
        }
    }
}