并查集与渗漏问题
前两周的时候看到有人推荐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
在优化上，我们强调两点：
- 带权重，永远把用元素大小小的小树的根节点去链接大树的根节点，这样可以降低树的深度，这样可以保证一棵树的深度最大不超过lgN，复杂度就随之下降了。
- 路径压缩，在找到根节点的同时，将结点移动至根节点，使得整个树变平。
渗漏 (Percolation) 问题
渗漏问题是并查集中的典型例题，在做的时候踩到了一个回流的小坑，其他也有一些小的优化点。
首先，从结果上来说，如果我们进行是否渗漏的结果检测，可能需要遍历首行和末行的结点，复杂度很高，因此虚拟一个头结点和一个尾结点，只需要考察它们俩是否连通，复杂度为 O(1)。
其次，基本上只要用二维数组去标记一个结点是否是open状态，但需要注意回流（backwash）的问题，具体表现为当有一条连通后，其他没有和头结点连通的孤立点也会在isFull是结果为true，这是因为并查集是无向的，它不会检验是否从该节点到头结点是否有通路。
因此我们用另一个并查集去检测是否isFull，这和原本的并查集的区别在于它没有尾结点，也就不会有回流，只需要检测是否和头结点相连即可。
代码 in Java
在 GitHub 仓库中了：
参考 & 扩展阅读
顺便还教了算法复杂度的分析方法，相当简单易懂，终于知道 lgN 是咋回事了！上一下自己没来得及读的内容吧。
植入部分
如果您觉得文章不错，可以通过赞助支持我。
如果您不希望打赏，也可以通过关闭广告屏蔽插件的形式帮助网站运作。