Jeremy Yu

title: 一文搞懂并查集 date: 2021-08-01 22:05:00 updated: 2021-08-01 22:05:00 photos:

https://img.yzmblog.top/blog/article_disjointset.jpg tags:
前端
Javascript
数据结构和算法 categories:
Javascript
数据结构和算法 excerpt: 并查集（Disjoint-set）是一种数据结构，从字面意思上看，“并”，“查”，“集”，可以简单地理解为：“合并”，“查找”，“集合”

并查集概念

并查集（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);

小结

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

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

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

Jeremy

Formal

Algorithm

Common

Docker

Javascript

Network

Node

Summary

notes

LowCodeProject

MCU

MC_MP_Programming

advancedAlgorithmicTech

algorithm

algorithmGameTheory

compilation

computerCompose

controlSystem

dataStructure

efficientAlgorithm

frontend

higherMath

javascript

linearMath

machineLearning

network

privacy_security

programming_language

researchMethod

typescript

videoEditor

vite

webassembly

webpack