并查集的正确使用姿势

因为工作的关系，不得不学习了几种算法，好久不用又忘记了，这是一篇复习文章。

并查集回答的是连接问题，比如说从 a 城到 b 城有没有路，能回答有或者没有，但是不能回答具体的路是那几条，该怎么走；再比如说 a、z 这 2 个人能否通过共同好友的名片分享来加上微信。

并查集是解决点与点之间的关系，遇到实际问题的时候，需要我们进行转换成点与点，也就是建模。在数据结构上一般用数组来存储这些点。

 let id = new Array(n); // 先用一个数组保留每个元素的父子关系，容量为 n
 for (var i = 0; i < n; i++) {
      id[i] = i; // 初始值是数组索引的位置，表示各不相连
   }

比如上面的微信加好友的例子中，我们需要把人与数字进行一下映射。看一下实际的例子。

let map = {
    a: 0, // 假设 a b c d 都是人，在数组的位置依次为 0 1 2 3
    b: 1,
    c: 2,
    d: 3
  };

  let uf = new UnionFind(4, i => map[i]);
  uf.union("a", "b");
  uf.union("b", "c");
  console.log(uf.connected("a", "c")); // true

并查集的实现代码不多，去掉一些非核心代码如下：

<script>
  function UnionFind(n, key) {
    var id, sz;
    key =
      key ||
      function(a) {
        return a;
      };

    id = new Array(n);
    sz = new Array(n);
    for (var i = 0; i < n; i++) {
      id[i] = i;
      sz[i] = 1;
    }

    this.find = function(p) {
      while (p != id[p]) {
        id[p] = id[id[p]]; // 路径压缩
        p = id[p];
      }

      return p;
    };

    this.connected = function(p, q) {
      p = key(p);
      q = key(q);
      return this.find(p) === this.find(q);
    };

    this.union = function(p, q) {
      p = key(p);
      q = key(q);
      var i = this.find(p),
        j = this.find(q);

      if (i === j) return;

      if (sz[i] < sz[j]) {
        id[i] = j;
        sz[j] += sz[i]; // 基于 size 的优化
      } else {
        id[j] = i;
        sz[i] += sz[j];
      }
    };
  }

  let map = {
    a: 0,
    b: 1,
    c: 2,
    d: 3
  };

  let uf = new UnionFind(4, i => map[i]);
  uf.union("a", "b");
  uf.union("b", "c");
  console.log(uf.connected("a", "c"));
</script>

优化手段

9. 基于 size 的优化
10. 基于 rank 的优化
11. 路径压缩

参考链接

• Implementation of Weighted Quick Union-Find with Path Compression data structure.
• 玩转算法系列，数据结构精讲。