union-find, quick-union, weighted-quick-union

[barretlee]

动态联通性这块的算法还是有点不好理解，下面是效率递增的三个算法：

• unionFind.js
• quickUnion.js
• weightedQuickUnion.js

回到家再继续分析这几个算法；）

function weightedQuickUnion(input, combo) {
  var sz = [];
  for(var i = 0, len = input.length; i < len; i++) {
    sz.push(1);
  }
  for(var i = 0, len = combo.length; i < len; i++) {
    var p = combo[i][0];
    var q = combo[i][1];
    if(root(p) != root(q)) {
      if(sz[p] > sz[q]) {
        sz[p] += sz[q];
        input[q] = p;
      } else {
        sz[q] += sz[p];
        input[p] = q;
      }
    }
  }

  return input;

  function root(n) {
    while(input[n] != n) {
      n = input[n];
    }
    return n;
  }
}

[barretlee]

动态联通图问题，需要将问题抽象成一个可编程的过程。书中提到触点、分量和连接，所以编程第一步，先初始化触点信息，简洁期间，每个触点信息保持跟他们的序号一样就行了。

• union find，大致意思就是将所有联通的节点信息归并为一个，有点类似于物理电路中的电势，让各点电势一样；
• quick union，将联通的两点按照顺序连接起来，有点像指针，a->b->c->d，保持串联，每次新的连接，都去判断两点的根指针是否一致，如果一致则略过，如果不一致则连接；
• weighted quick union，在上面算法的基础上，添加了权重判断，每个节点除了序号信息外，还有一个数深度信息（size），当指针不一致需要连接时，将深度小的数合并到大的上面（我觉得这一步有点难理解）。

研究算法的实现还是挺有意思的，最难的地方莫过于对复杂度的计算和判断。