引入逻辑结构:集合

将各个元素划分为若干个互不相交的子集

“并”操作 — > 让其中一棵树成为另一棵树的孩子

“查”操作 — >一个元素到底属于哪个集合 — > 找”根”

判断两个元素是否属于同一个集合 — > 两个元素根是否相同

这些操作也是”并查集” 名称的来源

我们考虑用双亲来表示树结构 这样可以很方便找到每个元素的根结点 构建起来也十分方便

下面是构建并查集的各个操作

1.初始化

将每个结点的双亲设为-1 表示单独成一个集合 每个元素都是根节点

2.”并”操作

这样的操作让root1成为root2集合的一部分

很明显 这样的并操作是可以优化的 因为我们需要树的深度尽可能小 因为这样可以减少复杂程度和遍历层数 下面是并操作的优化

因为root为负表示此节点为根结点 我们可以利用这个特点再利用负数大小表示集合所含元素个数 root越小说明集合中元素越多 就要让别的集合插入到该root集合中

3.”查”操作

思路很简单 循环遍历不断向上寻找 直到找到根节点为止

但是这个算法还可以优化 我们在寻找某个结点的根节点时可能会经过其他的多个节点 这些节点也是属于同一个根节点的 如果我们可以将这些节点直接挂到根节点下面 则可以大大减少循环遍历的次数

所以我们引入压缩路径的算法

从x结点 向上遍历 将只要在路径上不是根节点的结点全都挂在根节点下面即可

测试

并查集结构可视化:

输出结果:

根据图中所示 子节点和根节点都一一对应 测试通过