并查集概念

并查集（Disjoint-set）是一种数据结构，从字面意思上看，“并”，“查”，“集”，可以简单地理解为：“合并”，“查找”，“集合”。

• 集合，就是我们中学所学的一个概念，大概的理解就是把一对元素放在同一个地方。
• 合并，就是并集，意思是把两个集合合并在一起，例如：
  $$ { 1, 2, 3, 4 } \cup { 5, 6 } = { 1, 2, 3, 4, 5, 6 } $$
• 查找，需要查找什么？这里的查找指的是要查找这个元素在不在集合中，并且确定这个元素是在哪个集合中

归纳起来就是，并查集这个数据结构就是：

• 可以进行集合的合并操作
• 可以查找元素在哪个集合中
• 并查集维护的是一堆集合

并查集能解决什么问题

根据并查集的概念可以知道，他能查找一个元素是否在一个集合中，也能进行两个集合之间的合并。
他可以解决一些路径连接或者节点归属的问题。例如：

• 在两个局域网之间原本相互独立的，现在希望这两个局域网可以连接起来，而根据什么规则连接起来，可以使用并查集的合并操作。
• 当需要判断两台主机是否属于同一个局域网中。也可以使用并查集来判断。一些节点归属的问题，都可以使用并查集来解决

并查集的实现

介绍完并查集的一些概念，下面就来分析一下这个数据结构究竟是怎么实现的 根据上面例子来举一个例子：用并查集解决网络连接和网络归属的问题

• 首先我们定义 6 个节点[1，2，3，4，5，6]表示六台主机
• 将[1，2，3，4]四台主机按下图的方式连接起来，取名为局域网 A，其中节点 1 为根节点
• 同样地，将[5，6]两个节点也连接起来，取名为局域网 B，其中节点 5 为根节点

• 这样，主机 1，2，3，4 是属于同一个网络，主机 5，6 是同一个网络
  我们把这两个连通的主机分别放在两个集合中。
  $$A = {1,2,3,4}$$，$$B = {5, 6}$$
  如图所示

当两个局域网搭建完后，现在有人提出了几个问题：

• 1.已知所有的主机网络连接情况(比如上图的局域网 A：主机 3 和 2 是互联的，则可以表示[3, 2]，3 为父节点)，需要计算出一共有多少个网络？
• 2.判断主机 2和主机 4是否在一个局域网内。
• 3.如果主机 4和主机 6不在一个局域网内，怎样将这两个网络连接起来？

通过这几个节点来一步步实现并查集这个数据结构

计算每个节点的父节点（初始化）

首先来看第一个问题。

• 先把所有网络连接情况写出来，分别是：[0, 2], [2, 1], [2, 3], [4, 5]，其中: 数组的第一个元素是父节点，第二个元素是子节点。
• 第二步：用一维数组来记录下所有元素的父节点
• 当记录下所有元素的父节点时，由于根节点上不存在父节点，所以有多少个局域网的问题就可以转移为：数组中有多少个不存在父节点的元素 问题分析完了，开始用代码实现~

// 主机数量
const COMPUTER_NUM = 6;
// 主机连接关系
const connectLine = [
  // 数组的第一个元素是父节点，第二个元素是子节点
  [0, 2],
  [2, 1],
  [2, 3],
  [4, 5],
];

// 初始化记录父节点的数组，将所有数据主机的父节点设置为-1
// return [-1,-1,...,-1]
function init() {
  const arr = [];
  for (let i = 0; i < COMPUTER_NUM; i++) {
    arr.push(-1);
  }
  return arr;
}

// 记录每个节点的父节点
function fillParentNode(parentArr, connectLine) {
  connectLine.forEach((item) => {
    parentArr[item[1]] = item[0];
  });
}

// 查找又多少个父节点
function findParentNum(parentArr) {
  return parentArr.filter((index) => index === -1).length;
}

// 父节点
const parentArr = init();
// 填充父节点
fillParentNode(parentArr, connectLine);
console.log(parentArr); // [-1, 2, 0, 2, -1, 4]

// 查询有多少个父节点
const parentNum = findParentNum(parentArr);
console.log(`there are ${parentNum} networks`); // there are 2 networks

可以看到，先声明了一个用于装父节点的数组，并且默认值为-1，后面通过遍历讲所有主机的父节点记录到数组中，最后通过遍历数组统计父节点值还是-1 的数量，这个数量就是局域网的个数。
自此，第一个问题已经解决。

查找两个元素的根节点（查找节点）

继续来看看第二个问题：判断主机 2和主机 4是否在一个局域网内，再来回看上面的一个图，要判断两个主机是否在一个局域网内，问题可以转化为：这两个主机的根节点是否相同，如果相同则在同一个局域网中。

解决办法已经找到，接下来用代码实现，从上面已经实现的代码继续写下去。

// 实现一个查找根节点的方法
// @param { number } child 需要查找父节点的元素
// @param { array } parentArr 元素连接关系数组
// return number
function findRoot(child, parentArr) {
  let result = child;
  while (parentArr[result] !== -1) {
    result = parentArr[result];
  }
  return result;
}
// parentArr = [-1, 2, 0, 2, -1, 4]
const tag_2 = findRoot(1, parentArr);
const tag_4 = findRoot(3, parentArr);

console.log(`两台主机${tag_2 === tag_4 ? "在" : "不在"}同一个网络中`); // 两台主机在同一个网络中

通过不停地往上查找父节点，直到查找到定义元素的根节点后停止并返回。如果两台主机的根节点是相同的，则这两台主机在同一个集合中~反之则不在。
第二个问题也解决了。现在我们所定义的方法已经能够进行初始化和排序操作了。

两个网络连接（集合合并）

解决了查找的问题，接下来看第三个问题：

• 如果主机4和主机6不在一个局域网内，怎样将这两个网络连接起来？

要将两个网络连接起来的方法有很多，两个网络任意一个主机连接起来都会有变成一个局域网。 但我们需要找出他们之间效率最高的连接方法，如果我按下图的方法进行连接。

图中将局域网 B 的根结点连接到局域网 A 的 4 结点中，虽然两个网络连接起来了，但是这个网络的高度增加了（树的高度增加了），树的高度越高，查找越慢。从效率上看这种连接方法是不可取的。

要使树的效率高，应当减少树的高度。所依可以从两个树的根节点上连接，如下图

从第二个问题中已经实现了查找根元素的方法，接下来只要实现一个方法将两个根元素合并起来就行了。

// 合并方法
// @param { number } x 主机x
// @param { number } y 主机y
// @param { parentArr } parentArr 父节点
// return boolean
function unionSet(x, y, parentArr) {
  // 找出两个主机的根节点
  const x_root = findRoot(x, parentArr);
  const y_root = findRoot(y, parentArr);

  // 如果两个根节点相同，则他们在同一个网络中，不需要合并
  if (x_root === y_root) {
    return false;
  } else {
    parentArr[x_root] = y_root;
    return true;
  }
}

unionSet(3, 5, parentArr); // true
console.log(parentArr); // [4, 2, 0, 2, -1, 4]

到这里，两个网络已经成功合并起来了。

优化合并（路径压缩）

从代码中可以看到，虽然从根节点上连接起来，但是它的时间复杂度为O(n)，当有多个网络需要连接起来时，性能可能会不够好。
再来分析一下，并查集主要的函数是并(union) 和 查（find）。 查找方法中，我们只需要找到元素的根节点,无需关心元素的父节点，那么我们在记录节点关系的时候只要记住节点的根节点就行了，如下图：

接下来修改一下代码：

合并方法修改

// 合并方法
// @param { number } x 主机x
// @param { number } y 主机y
// @param { parentArr } parentArr 父节点
// @param { rankArr } 树的高度数组
// return boolean
function unionSet(x, y, parentArr, rankArr) {
  // 找出两个主机的根节点
  const x_root = findRoot(x, parentArr);
  const y_root = findRoot(y, parentArr);

  // 如果两个根节点相同，则他们在同一个网络中，不需要合并
  if (x_root === y_root) {
    return false;
  } else {
    // 高度小的向高度大的合并
    if (rankArr[x_root] > rankArr[y_root]) {
      parentArr[y_root] = x_root;
    } else if (rankArr[x_root] < rankArr[y_root]) {
      parentArr[x_root] = y_root;
    } else {
      // 高度相同随机合并，并且被合并的深度加1
      parentArr[x_root] = y_root;
      rankArr[y_root]++;
    }
    return true;
  }
}

初始化方法修改

// 初始化记录父节点的数组，将所有数据主机的父节点设置为-1
// return [-1,-1,...,-1]
function init() {
  const arr = [];
  const rankArr = [];
  for (let i = 0; i < COMPUTER_NUM; i++) {
    arr.push(-1);
    rankArr.push(0);
  }
  return [arr, rankArr];
}

记录父节点的方法修改

// 记录每个节点的父节点
function fillParentNode(parentArr, rankArr, connectLine) {
  connectLine.forEach((item) => {
    unionSet(item[1], item[0], parentArr, rankArr);
  });
}

代码修改完了，现在来试一下

// 调用合并方法，合并主机4和主机6所在的集合
unionSet(3, 5, parentArr, rankArr); // true
console.log(parentArr); // [4, 0, 0, 0, -1, 4]

合并后的网络如下图：

显然与为优化相比，树的高度减少了。而且时间复杂度也变为O(a(n))

完整代码

// 初始化记录父节点的数组，将所有数据主机的父节点设置为-1
// return [-1,-1,...,-1]
function init() {
  const arr = [];
  const rankArr = [];
  for (let i = 0; i < COMPUTER_NUM; i++) {
    arr.push(-1);
    rankArr.push(0);
  }
  return [arr, rankArr];
}

// 记录每个节点的父节点
function fillParentNode(parentArr, rankArr, connectLine) {
  connectLine.forEach((item) => {
    unionSet(item[1], item[0], parentArr, rankArr);
  });
}

// 查找又多少个父节点
function findParentNum(parentArr) {
  return parentArr.filter((index) => index === -1).length;
}

// 实现一个查找根节点的方法
// @param { number } child 需要查找父节点的元素
// @param { array } parentArr 元素连接关系数组
// return number
function findRoot(child, parentArr) {
  let result = child;
  while (parentArr[result] !== -1) {
    result = parentArr[result];
  }
  return result;
}

// 合并方法
// @param { number } x 主机x
// @param { number } y 主机y
// @param { parentArr } parentArr 父节点
// @param { rankArr } 树的高度数组
// return boolean
function unionSet(x, y, parentArr, rankArr) {
  // 找出两个主机的根节点
  const x_root = findRoot(x, parentArr);
  const y_root = findRoot(y, parentArr);
  // 如果两个根节点相同，则他们在同一个网络中，不需要合并
  if (x_root === y_root) {
    return false;
  } else {
    // 高度小的向高度大的合并
    if (rankArr[x_root] > rankArr[y_root]) {
      parentArr[y_root] = x_root;
    } else if (rankArr[y_root] > rankArr[x_root]) {
      parentArr[x_root] = y_root;
    } else {
      // 高度相同随机合并，并且被合并的深度加1
      parentArr[x_root] = y_root;
      rankArr[y_root]++;
    }

    return true;
  }
}

/*
 * 测试
 */
// 主机数量
const COMPUTER_NUM = 6;
// 父节点
const [parentArr, rankArr] = init();
// 填充父节点
fillParentNode(parentArr, rankArr, connectLine);

unionSet(3, 5, parentArr, rankArr);

小结

本文主要介绍了并查集的概念，作用和实现。并查集他是一种数据结构，能查找出某两个节点是否在同一个集合中。
并查集的关键是

• 可以进行集合的合并操作
• 可以查找元素在哪个集合中
• 并查集维护的是一堆集合

若文章中有不严谨或出错的地方请在评论区域指出~

参考

1. 并查集（Disjoint-set）
2. 并查集能干点啥？