关于 并查集 - 代码中的等价关系

今日的每日一题是

因为最近的题都和离散数学有关,一看到题我就想起了最近学的离散数学中的等价关系,于是想有么有一种可以表示 A 上的一个等价闭包的数据结构。
经过百度之后,我找到了并查集这种数据结构,感觉可以实现一个等价闭包,特此记录下来。

并查集属于第三级的数据结构 —— 这是我自己想的数据结构分级:

  • 一级数据结构为树,链表和数组,这种是各种代码原生就可以实现,不用引入库。
  • 二级数据结构是无序哈希表,栈,队列等对一级数据结构进行了初步封装,一般各种语言自带这种数据结构的库。
  • 三级数据结构就是为了实现特定的逻辑,需要我们灵活使用一二级的数据结构来封装的一种,这类数据结构一般语言没有自带库。

在打题或者面试的时候,一二级数据结构通常我们可以直接调用库,而三级数据结构需要我们自己去实现。并查集就是第三级的数据结构。

等价关系

等价关系为 A 上的一个具有自反性、对称性、传递性的一个关系 R 。具体有如下性质:

1
2
3
1. 对于所有 a ∈ A, 关系 <a,a> 一定 ∈ R ,对应自反性。
2. 如果 <a,b> ∈ R ,则 <b,a> 也 ∈ R ,对应对称性。
3. 如果 <a,b> ∈ R 且 <b,c> ∈ R ,则 <a,c> 也 ∈ R ,对应传递性。

如果一个关系满足以上条件,则该关系为等价关系。

等价闭包

对于 A 上任意一个关系 R,R 可能不是等价关系。如果往 R 中加入最少的序偶,使得新的 R 变为等价关系,则这个新的 R 为原来 R 的等价闭包。

例如:

1
2
A = {a ,b ,c}
R = {<a,a> ,<b,b> ,<a,b> ,<b,a>}

我们可以看到 R 是 A 上一个二元关系,但是 R 并不是等价关系,因为 <c,c> ∉ R,不满足上面条件 1。而我们只要往 R 中加入一个 <c,c> 变为 R’ :

1
2
3
A = {a ,b ,c}
R = {<a,a> ,<b,b> ,<a,b> ,<b,a>}
R' = {<a,a> ,<b,b> ,<a,b> ,<b,a> ,<c,c>}

可以看到 R’ 符合等价关系的条件,所以 R’ 为 R 的等价闭包。

并查集

并查集其实可以抽象为一个森林图,并且其中每棵树都是根树,例如下图:

其实等价关系可以理解为一种类似江湖间的朋友机制,江湖里英雄们都很讲义气,他们有以下信条:

  1. 我是我自己的朋友
  2. 你把我当朋友,我也一定把你当朋友
  3. 朋友的朋友也是我的朋友

这三条分别对应着等价关系三条规则,那么问题来了,任意给定两个人,怎么判断他们是不是朋友呢 ?

这个模型可以用上面的有向图解决,首先各个点对应着各个人,其次,a 和 b 之间有箭头代表他们一定是朋友 。其次,因为有第三条,朋友的朋友也是朋友,所以最终一定会形成这样一种树状的结构,只要两个点在同一条树上,则两个人就是朋友,这也是并查集用来表示等价关系的原理。

查找和合并

并查集拥有两个操作:

一是查找,则给定 a 和 b ,判断 <a,b> 是否 ∈ R,回到刚刚的有向图,则问题等价于 a 和 b 是否在同一颗树上。具体做法是对 a 和 b 分别向上取父节点,最终会取到某一棵树的根节点,如果 a 和 b 的根节点为同一个点,则 a 和 b 在同一棵树内,则 <a,b> ∈ R ,否则反之。根据题目的特殊性,有可能需要对查找到的两个根节点进行相关操作,具体要看具体问题。

二是合并,还是以最初的关系为例:

1
2
A = {a ,b ,c}
R = {<a,a> ,<b,b> ,<a,b> ,<b,a> ,<c,c>}

R 为等价关系,此时我门把 <b,c> 加入 R 中,可以看到加入后 R 肯定不是等价关系,而我们此时对新的 R 取等价闭包,最终会形成以下的新关系:

1
2
3
4
A = {a ,b ,c}
R = {<a,a> ,<b,b> ,<a,b> ,<b,a> ,<c,c>}
R' = {<a,a> ,<b,b> ,<a,b> ,<b,a> ,<c,c>
,<b,c> ,<c,b> ,<a,c>}

新的 R’ 依然是一个等价关系,这就是合并操作,对于并查集,我们把 b 和 c 合并相当于把 <b,c> 加入到关系中并对新关系取闭包。

例如以下的并查集图:

我们对 b c 进行合并操作,相当于想办法让 b 和 c 处于同一棵树内,且不破坏原本的关系,即对于除 b c 外其他任何一个元素,原来在一棵树上的,现在依然也在一棵树上。

其实操作也并不难,首先先获取 b 和 c 的根,对于上图则分别为 b本身 和 a,而我们只要让其中一个作为另一个的父节点即可,例如我们可以将 b 作为 a 的一个子节点。

完美,b 和 c 现在在同一颗树内了,并且原本的关系也没有被破坏。

应用

理论知识完了,接下来上一下应用把,(代码实现已经效率优化的等力扣题目的记录)

题目描述

  • 给定一个由表示变量之间关系的字符串方程组成的数组,每个字符串方程 equations[i] 的长度为 4,并采用两种不同的形式之一:"a==b""a!=b"。在这里,ab 是小写字母(不一定不同),表示单字母变量名。

  • 只有当可以将整数分配给变量名,以便满足所有给定的方程时才返回 true,否则返回 false

输入示例

1
2
3
输入:["a==b","b!=a"]
输出:false
解释:如果我们指定,a = 1 且 b = 1,那么可以满足第一个方程,但无法满足第二个方程。没有办法分配变量同时满足这两个方程。
1
2
3
输出:["b==a","a==b"]
输入:true
解释:我们可以指定 a = 1 且 b = 1 以满足满足这两个方程。
1
2
输入:["a==b","b==c","a==c"]
输出:true
1
2
输入:["a==b","b!=c","c==a"]
输出:false
1
2
输入:["c==c","b==d","x!=z"]
输出:true

思路

这题粗一看好像要代入数据看是否矛盾,实际上没必要。首先根据 等于 这个关系的性质,等于 关系是一个等价关系。

因为 = 满足以下条件:

  1. a = a ,对应等价关系第一条
  2. 如果 a = b 则 b = a ,对应等价关系第二条
  3. 如果 a = b , b = c 则 a = c ,对应等价关系第三条

对于这个等价关系,这里的 A 是 26 个小写的英文字母。

而对于本题,如果要返回 false ,则必须满足以下条件:

  • a != b 且 a == b 。其中 a == b 可能不在它给的条件中,但是可以由等价关系得出(一般是利用第三条得出的)

那思路就有了,首先先遍历一遍所有 a==b 的式子,把 <a,b> 加入到一个关系 R 中,全部加入后,对 R 取等价闭包 R’ 。

再次遍历所有 a!=b 的式子,判断序偶 <a,b> 是否在 R’ 中,如果存在,则 返回 false ,如果所有都不存在,则返回 true 。

对于程序来说,就需要用到并查集这样的结构,对于以上来说,加入取闭包为对并查集进行合并操作,判断是否在里面则为对并查集的查找操作。

首先新建一个容量为 26 分别对应 26 个英文字母的并查集 —— 并查集因为是对应等价关系,而等价关系是在一个集合上的二元关系,所以需要指定集合 A 。在代码中,可以直接设定容量,然后根据下标数字来对应自己想要的东西。

这样一来,循环遍历两次,第一次只遍历 a==b 的情况,然后对并查集进行合并 a 和 b 的操作。第二次只遍历 a!=b 的情况,然后对并查集进行查找 a 和 b 的操作,如果有一个 a 和 b 属于同一个根节点,则返回 false ,否则返回 true。

后记

并查集属于三级数据结构,打题的时候需要自己实现。虽然并查集是有向图的一种树,但是我们一般不用树这种数据结构,一般比较常用的为数组和哈希表。除此之外。容易看出,查找某两个值的时候,需要一直往上找到根节点,所以并查集的效率取决于树的高度,然后就衍生出一系列减少树高度的优化措施,具体之后到代码实践的时候在说吧。