Javascript 数据结构之图 这篇文章中我们学习了有关图的一些算法和相关知识:图的遍历、最小生成树和最短路径等。本文继续介绍数据结构的高级算法:并查集。完整代码可到 Github 上查看。

并查集 Disjoint Sets

并查集是一种用于处理一些不交集合(Disjoint Sets)的合并和查询问题的数据结构。并查集有两个主要的操作:

1、 查找(Find):确定元素属于哪个子集。可以用来确定两个元素是否属于同一子集。

2、 合并(Union):将两个子集合并成同一个集合。

除了上述两种操作,并查集还有一个重要的方法——MakeSet——用于建立元素集合。在集合中选定一个固定的元素作为整个集合的代表,Find(x)返回 x 所属集合的代表,Union 使用两个集合的代表为入参进行集合的合并操作。下面让我们通过一个列子来理解并查集。

  1. Disjoint Sets Data Structure - Weighted Union and Collapsing Find YouTube

如上图所示,我们有一个非连通无向图,该图有两个连通分量,我们用两个集合表示这两个连通分量:

$S_{1}= ${ 1,2,3,4 } 和 $S_{2}=${5,6,7,8}。集合中的元素代表连通分量的顶点。

如果对$S_{1}$和$S_{2}$取交集,很明显这两个集合的交集为空集: $S_{1}\cap S_{2}= \oslash $,这就是 disjoint set 不交集。

如果想确定顶点 5 属于哪个连通分量,我们可以在$S_{1}$和$S_{2}$中进行查找(Find)操作,最终我们将确定顶点 5 属于集合$S_{2}$。

假设,我们将连通顶点 4 和顶点 8,如下图所示:

连通后我们得到一条边$\left ( 4,8\right )$,通过 Find(x) 操作,可知顶点 4 在集合$S_{1}$中,顶点 8 在集合$S_{2}$中,两个顶点位于不同的集合中,所以我们将进行 Union 操作,合并集合$S_{1}$和$S_{2}$,得到集合$S_{1}\cup S_{2}= ${1,2,3,4,5,6,7,8},将新集合命名为$S_{3}$,此时集合中已经包含了图中所有的顶点。

接下来我们继续连通顶点 1 和顶点 5,如下图所示:

现在我们得到边$\left ( 1,5\right )$,通过 Find(x)操作,发现这两个顶点同属于集合$S_{3}$,这说明此时图中存在了回路。

检测回路

Javascript 数据结构之图 中我们曾介绍过最小生成树 Kruskal 算法,该算法按权值从小到大依次作为最小生成树的边,当某条边生成回路时,不能选用为最小生成树的边。如何判断无向图中是否存在回路,就可以用到并查集的特性。现在通过一个例子来看看如何检测回路。

如上图所示,是一个无向网,我们需要找到该图的最小生成树。首先我们依次选取权重最小的边并用边的顶点建立集合。

权重最小的边为$\left ( 1,2\right )$,得到集合$S_{1}= ${ 1,2 };

权重第二小的边为$\left ( 3,4\right )$,得到集合$S_{2}= ${ 3,4 };

权重第三小的边为$\left ( 5,6\right )$,得到集合$S_{3}= ${ 5,6 };

权重第四小的边为$\left ( 7,8\right )$,得到集合$S_{4}= ${7,8 };

权重第五小的边为$\left ( 2,4\right )$,此时顶点 2 在$S_{1}$中,顶点 4 在$S_{2}$,两个顶点在不同的集合中,所以需要进行 Union 合并操作,将$S_{1}$与$S_{2}$合并得到集合$S_{5}=${1,2,3,4};

权重第六小的边为$\left ( 2,5\right )$,此时顶点 2 在$S_{5}$中,顶点 5 在$S_{3}$,两个顶点在不同的集合中,所以需要进行 Union 合并操作,将$S_{5}$与$S_{3}$合并得到集合$S_{6}=${1,2,3,4,5,6};

权重第七小的边为$\left ( 1,3\right )$,此时顶点 1 和顶点 3 在同一个集合$S_{6}$中,意味着存在回路,所以最小生成树不能包含此条边;

权重第八小的边为$\left ( 6,8\right )$,此时顶点 6 在$S_{6}$中,顶点 8 在$S_{4}$,两个顶点在不同的集合中,所以需要进行 Union 合并操作,将$S_{6}$与$S_{4}$合并得到集合$S_{7}=${1,2,3,4,5,6,7,8};

最后一条边为$\left ( 5,7\right )$,顶点 5 和顶点 7 在同一个集合 $S_{7}$中,意味着此时存在了回路,所以最小生成树不能包含此条边;

到此为止我们已经遍历了无向图的所有边,并且得到了最小生成树构成的边。接下来让我们继续学习如何图形化表示并查集。

图形化表示

我们继续以上一节的无向网为例,上一节中我们构造集合来判断两个点是否存在于同一个集合构成回路,本节中,我们将不去构造具体的集合,而是使用一个元素来代表集合。还是以生成最小生成树为例。

首先选取权重小的边$\left ( 1,2\right )$,将顶点 1 作为父节点,顶点 2 作为子节点构造一颗树形结构;

选取权重第二小的边为$\left ( 3,4\right )$,将顶点 3 作为父节点,顶点 4 作为子节点构造一颗树形结构;

选取权重第三小的边为$\left ( 5,6\right )$,将顶点 5 作为父节点,顶点 6 作为子节点构造一颗树形结构;

选取权重第四小的边为$\left ( 7,8\right )$,将顶点 7 作为父节点,顶点 8 作为子节点构造一颗树形结构,结果如下图所示,其中父节点将作为集合的代表:

权重第五小的边为$\left ( 2,4\right )$,顶点 2 的父节点为顶点 1,顶点 4 的父节点为顶点 3,分别在不同的集合中,所以需要进行合并,此时因为两颗树的深度是一样的,所以顶点 1 作为父节点和顶点 3 作为父节点都可以,我们以顶点 1 作为父节点为例:

此时依然是每棵树的父节点作为该集合的代表。继续构造最小生成树:

权重第六小的边为$\left ( 2,5\right )$,顶点 2 的父节点为顶点 1,顶点 5 本身是父节点,分别在不同的集合中,所以需要进行合并,此时因为顶点 1 位代表的树的深度大于顶点 5,所以将顶点 5 合并到顶点 1(这么做的理由将在 Rank 合并小节中进行讲解):

继续选择权重第七小的边为$\left ( 1,3\right )$,由于顶点 1 和顶点 3 均在顶点 1 代表的集合中,此时将存在回路,最小生成树不能包含此条边;

同理边$\left ( 7,8\right )$将被合并到顶点 1 代表的集合:

接下来,我们用数组来实现上述同样操作。

数组化表示

本节还是以检测回路小节中的无向网为例,首先我们构造一个数租,名字为 parent,数组中的每一项代表图中的顶点,值代表顶点的父节点,-1 表自己是父节点:

首先选取权重小的边$\left ( 1,2\right )$,将顶点 1 作为父节点,顶点 2 作为子节点,更新数组中顶点 1 和顶点 2 的中,顶点 2 的父节点为 1,顶点 1 的值为-2,负数表示该顶点是父节点,负数的绝对值表示该顶点代表的集合包含的顶点个数:

重复同样的步骤修改边$\left ( 3,4\right )$、$\left ( 5,6\right )$、$\left ( 7,8\right )$中顶点在数组中的值:

权重第五小的边为$\left ( 2,4\right )$,顶点 2 的父节点为 1,顶点 4 的父节点为 3,顶点 3 的父节点是自身,两个不同的父节点,进行合并操作,使顶点 3 的父节点为顶点 1,顶点 1 为代表的集合中包含了 4 个点:

权重第六小的边为$\left ( 2,5\right )$,顶点 2 的父节点为 1,顶点 5 自身为父节点,同样两个不同的父节点需要进行合并操作:

继续选择权重第七小的边为$\left ( 1,3\right )$,顶点 1 自身为父节点,顶点 3 的父节点是顶点 1,相同的父节点,说明两个顶点在同一个集合中,存在回路。

权重第八小的边为$\left ( 6,8\right )$,顶点 6 的父节点是 5,顶点 8 的父节点是 7,顶点 5 的父节点是 1,顶点 7 的父节点是自身,两个不同的父节点,合并:

Rank 合并

合并时将元素所在深度小的集合合并到元素所在深度大的集合。这样我们可以保证树不会越来越深,查询的路径不会越来越长。所以在图形化表示的小节中,我们将深度小的树作为子树进行合并。

路径压缩查找

压缩同样是为了优化查询效率。在数组化表示的小节中,最后得到的数组中,所以元素的父节点都可以直接或间接的指向顶点 1,那么,我们是否可以将那些间接指向顶点 1 的点的父节点也改为顶点 1,以优化查询效率:

这便是路径压缩的思想。

参考文献

  1. 并查集 wiki