并查集与渗漏问题

前两周的时候看到有人推荐https://www.coursera.org/learn/algorithms-part1/的算法课,正好基础也忘得差不多了,觉得也是应该复(yu)习(xi)一下了,普林斯顿的这个公开课确实不错。

好了,废话不多说,来总结一下第一周,说说并查集和渗漏问题吧。

数据结构介绍

并查集是一个处理连接问题的数据结构,可以用这个结构快速的找到两个元素是否属于同一集合(或者说连通),和图的连通算法不同的是它忽略了路径的概念,只需要结果。

下面是一段来自 wiki 的解释。

在计算机科学中,并查集是一种树型的数据结构,其保持着用于处理一些不相交集合(Disjoint Sets)的合并及查询问题。有一个联合-查找算法(union-find algorithm)定义了两个操作用于此数据结构:
Find:确定元素属于哪一个子集。它可以被用来确定两个元素是否属于同一子集。
Union:将两个子集合并成同一个集合。
因为它支持这两种操作,一个不相交集也常被称为联合-查找数据结构(union-find data structure)或合并-查找集合(merge-find set)。其他的重要方法,MakeSet,用于建立单元素集合。有了这些方法,许多经典的划分问题可以被解决。

算法及其优化

Quick-Find

Quick-Find在联合 (Union) 时需要遍历每一项,找到和待改变的元素对应组相同的元素,将他们修改为同一组,所以时间复杂度为 O(n),在查找时可以直接判断两个元素的组号是否相等,所以时间复杂度为 O(1)。

Quick-Union

Quick-Union是一种树形结构,他不需要将每一项都进行修改,只需要B的根节点联合到A树上,因此在联合上少了一些工作量,但是因此,在查找时,需要查找两树是否出自同一根节点,在寻找根的过程中,复杂度一定会比原来的 O(1) 高,由此带来了新的麻烦:树的深度可能会影响我们的时间复杂度。

Weighted-Quick-Union

在优化上,我们强调两点:

  1. 带权重,永远把用元素大小小的小树的根节点去链接大树的根节点,这样可以降低树的深度,这样可以保证一棵树的深度最大不超过lgN,复杂度就随之下降了。
  2. 路径压缩,在找到根节点的同时,将结点移动至根节点,使得整个树变平。

渗漏 (Percolation) 问题

渗漏问题是并查集中的典型例题,在做的时候踩到了一个回流的小坑,其他也有一些小的优化点。

首先,从结果上来说,如果我们进行是否渗漏的结果检测,可能需要遍历首行和末行的结点,复杂度很高,因此虚拟一个头结点和一个尾结点,只需要考察它们俩是否连通,复杂度为 O(1)。

其次,基本上只要用二维数组去标记一个结点是否是open状态,但需要注意回流(backwash)的问题,具体表现为当有一条连通后,其他没有和头结点连通的孤立点也会在isFull是结果为true,这是因为并查集是无向的,它不会检验是否从该节点到头结点是否有通路。

因此我们用另一个并查集去检测是否isFull,这和原本的并查集的区别在于它没有尾结点,也就不会有回流,只需要检测是否和头结点相连即可。

代码 in Java

在 GitHub 仓库中了:

参考 & 扩展阅读

顺便还教了算法复杂度的分析方法,相当简单易懂,终于知道 lgN 是咋回事了!上一下自己没来得及读的内容吧。

如果您觉得文章不错,可以通过赞助支持我

标签: 知识, 题目, 算法

添加新评论