Union Find 数据结构和算法理解

最近开始学习一些不那么简单的算法，比如上一篇中的Graph就是一种不那么容易理解和学习的数据结构，今天来学习另一种数据结构和算法。

Union-Find这种算法的有哪些特点呢？

1、用最少的代码解决相对复杂的问题，而且时间和空间复杂度还相当优异。

2、这种算法能解决类似问题，比如：给定一组顶点和边，找出哪些组件属于同一个组，及存在多少个这样的组？

3、这种算法的另一个名称："Disjoint Set"。

Union-Find算法的核心操作有哪些？

1、基本思想是使用数组（或类数组）数据结构模拟森林（一组树）。数组的索引代表节点。数组的值代表每个节点的父节点。

2、例如，如果 array[i] == i，则表示节点 i 是该组的父节点。如果 array[i] == j 且 i != j，则表示节点 i 指向节点 j，即节点 j 是节点 i 的父节点。

3、所以要找到节点 i 的父节点，我们可以从索引 i 向上遍历，直到遇到 array[j] == j，这意味着我们找到了 i 所在组的父节点。

4、总结下来，此算法有两个核心操作，那就是find以及union。

require("@fatso83/mini-mocha").install();
const { expect } = require('chai');
class UF {
  constructor(N){
    //存储父节点
    this.parent = Array.from({ length: N }, (_, i) => i);
    //代表所属的组有多少个元素
    this.count = new Array(N).fill(1);
  }

  /**
   * 寻找一个节点的最终父节点
   */
  find(x) {
    if (this.parent[x]!==x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x]
  }

  union(x, y){
    const xp = this.find(x), yp = this.find(y);
    if (xp == yp) return;
    if (this.count[xp] < this.count[yp]) {
      //说明yp节点是父节点，需要合并到yp节点所属的组中
      this.parent[xp] = yp;
      this.count[yp] += this.count[xp];
    } else {
      //合并到xp节点所属的组中
      this.parent[yp] = xp;
      this.count[xp] += this.count[yp];
    }
  }

  group() {
    return this.parent.filter((item,index)=>item==index).length;
  }
}

/**
 * 增加了一个单元测试
 */
describe('test UF', function(){
  
  it('test union of uf',()=>{
    const uf = new UF(10);
    uf.union(1,3);
    uf.union(2,3);
    uf.union(3,4);
    uf.union(7,8);
    expect(uf.group()).to.equal(6);
  });
  it('test find of uf',()=>{
    const uf = new UF(10);
    uf.union(1,3);
    uf.union(2,3);
    uf.union(3,4);
    uf.union(7,8);
    expect(uf.find(4)).to.equal(1);
    expect(uf.find(8)).to.equal(7);
  });
});

下面再来看看另一个例子：

const countComponents = function(n, edges) {
  const UF = Array.from({ length: n }, (_, i) => i);
  edges.forEach(([e1, e2]) => union(e1, e2));
  return UF.filter((c, i) => c == i).length;

  function union(c1, c2) {
    const p1 = find(c1), p2 = find(c2);
    if (p1 != p2) UF[p1] = p2;
  }

  function find(c) {
    if (c != UF[c]) UF[c] = find(UF[c]);
    return UF[c];
  };
};

这里例子的作用其实就是在一个无向图中，如果节点连接在一起算一个组件的话，那么这个方法就是计算出有多少个组件？大家认真想想，是不是和webpack中打包的时候，计算有多少个Chunck很像，也许webpack就是这样计算的。哈哈，猜的，如果有知道的，欢迎讨论。

这里再用另外一个例子来解释这个算法的作用：

require("@fatso83/mini-mocha").install();
const { expect } = require('chai');
class UF {
  constructor(N){
    //存储父节点
    this.parent = Array.from({ length: N }, (_, i) => i);
    //代表所属的组有多少个元素
    this.count = new Array(N).fill(1);
  }

  /**
   * 寻找一个节点的最终父节点
   */
  find(x) {
    if (this.parent[x]!==x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x]
  }

  union(x, y){
    const xp = this.find(x), yp = this.find(y);
    if (xp == yp) return;
    if (this.count[xp] < this.count[yp]) {
      //说明yp节点是父节点，需要合并到yp节点所属的组中
      this.parent[xp] = yp;
      this.count[yp] += this.count[xp];
    } else {
      //合并到xp节点所属的组中
      this.parent[yp] = xp;
      this.count[xp] += this.count[yp];
    }
  }

  group() {
    return this.parent.filter((item,index)=>item==index).length;
  }
}

const arrs = ["tars","rats","arts","star"];
//比较两个字符串是否相似
const isSimilar = (str1, str2)=>{
  const obj = {};
  let counter = 0;
  for (let i = 0 ; i < str1.length ; i++) {
    if (str1[i] !== str2[i]) {
      counter++;
      obj[str1[i]] = str2[i];
    }
  }
  return (counter === 2 && oppositeObj(obj))? true : false
}

const oppositeObj = (obj)=>{
  const keys = Object.keys(obj);
  const length = keys.length;
  if (length!=2){
    return false;
  }
  if (obj[keys[0]] !== keys[1]) {
    return false;
  }
  return true;
}

describe('pars-keys test',()=>{
  it('pars-keys obj={} test',()=>{
    const obj = {};
    const result = oppositeObj(obj);
    expect(result).to.equal(false);
  });
  it('pars-keys obj not two keys test',()=>{
    let obj = {
      'a': 'c'
    };
    const result = oppositeObj(obj);
    expect(result).to.equal(false);
    let obj1 = {
       'a': 'c',
       'b': 'b',
       'c':'a'
    };
    const result1 = oppositeObj(obj1);
    expect(result1).to.equal(false);
  });
  it('pars-keys obj has two key test',()=>{
    let obj = {
      'a':'c',
      'b':'c'
    }
    const result = oppositeObj(obj);
    expect(result).to.equal(false);
    let obj1 = {
      'a':'c',
      'c': 'a'
    }
    const result1 = oppositeObj(obj1);
    expect(result1).to.equal(true);
  });
});
describe('similar string group test',()=>{
    it('UF group test',()=>{
        const uf = new UF(4)
        for (let i = 0 ; i < arrs.length; i++) {
          for (j = i+1; j < arrs.length; j++) {
            if (isSimilar(arrs[i], arrs[j])) {
              uf.union(i,j);
            }
          }
        }
        expect(uf.group()).to.equal(2);  
    });
});