5c919b295301410758487bcc991d1622
并查集(union-find)算法介绍

并查集(union-find)算法介绍

这些文章转自公众号:《让技术一瓜共食》,id:tech_gua,关注公众号可免费阅读这些文章。小专栏有独家的习题集和习题解答,会帮你掌握这些知识点。

在 LeetCode 上有一道题 LeetCode-547 朋友圈,题目大意是这样:

班上有 N 名学生。其中有些人是朋友,有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友,B 是 C 的朋友,那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈,是指所有朋友的集合。

这题最后让我们求得集合数。其实无论在工作中还是在生活中,这种分组问题十分常见。我们当然可以把每一类东西往一个 Array 或者是 Set 中塞入,然后不断的去搜每一个集合是否有关联进而合并组,最终也可求得分组数。但是拍脑袋想,我们要遍历 N 次每个集合,真的是一个超级耗时的办法。

那么有什么更加优美的数据结构来解决这类问题呢?其实就是今天要讲的并查集(union-find)

并查集是什么?

并查集是用来管理元素分组状况的数据结构。并查集可以高效地执行如下操作。不过需要注意并查集虽然可以进行合并操作,但是无法进行分割操作。

  • 查询元素 a 和元素 b 是否属于同一组
  • 合并 a 和 b 所在的组

并查集的结构

使用树形结构来实现,但不是二叉树。

每个元素对应一个节点,每个组对应一棵树。在并查集中,哪个节点是哪个节点的父亲以及树的星中信息无需多加关注,树形结构这个整体才是最重要的

1. 初始化

我们准备 n 个节点来表示 n 个元素,最开始没有边。

2. 合并

例如下图,从一个组的根向另一个组的根相连,这样两棵树就变成了一棵树,也就把两个组合并为一个组了。

其实我们发现合并并没有一个固定的规律,只要将两棵不规则树合起来就好。

3. 查询

为了查询两个节点是否属于同一个组,我们需要沿着树向上走,来查询包含这个元素的树的根是谁。如果两个节点走到了同一根,那么就说明它们属于同一组。

例如下图中,元素 2 和元素 5 都走到了元素 1,因此它们属于同一组。另一方面,由于元素 7 走到的是元素 6 ,因此同元素 2 或元素 5 属于不同组。

实现

好了,这种场景我们需要怎样实现呢?是否需要一个复杂的树来做呢?其实不用,请记住:虽然我们的思路是通过树型结构来解决,但是代码实现永远不要局限于思路。类似于二叉树,我们同样的也可以通过一维数组来实现,并查集也是如此。

top Created with Sketch.