1. 介绍

本系列关于算法的笔记是记录自己学习Sedgewick的《算法》第四版的学习笔记。本节将介绍UNION-FIND的这个具体算法的例子来了解基本的算法设计和分析方法。

2.动态连接(dynamic connection)

这是一类问题模型,寻求连通性的。寻求某两个节点之间是否有通路。
可以运用在社交网络、计算机网络等。

2.1 解决步骤

  1. 分解成多个连接单元 节点之间符合自反对称和传递性。这样可以分解成多个连接单元,例如:


2.对进行连接的节点只要对他们的连接单元进行并操作即可
当要把2,5连接起来的时候,对连接单元进行并操作即可。

2.2 总结

该方法通过并操作,能迅速进行连通性测试,但是无法给出路径。下面的内容将给出这种思路的不同实现方法。

3. Quick Find

通过构造一个数组(初始化的时候里面的内容为0到N),能连通的话则数组内的值需要修改成一样。


此时要连接6,1的话,则我们需要修改数组中0,5,6下标的值。(下标对应节点的值)

该算法比较容易,但是需要很多修改,数据量大的时候效率低。该算法的时间复杂度为N^2。在实际环境中要尽量避免N^2复杂度的算法。因为效率还是不够高。

4. Quick Union

采用树形结构。我们仍然使用一个数组,数组中保存的是其节点父亲节点的值。通过判断是否存在相同的根节点(是最上面的根节点哦!)来判断连通性。这种方式进行UNION操作的时候就很方便了,只要修改一个连接单元的根节点为另一个连接单元的根节点,也就意味着把两个连接单元给UNION了。根节点的根节点就是自己。

优缺点:相比quick find,该算法在一般情况下是会比其效率高,但是如果树太高了(最坏情况下),这种时候的时间复杂度仍然为O(N^2)

4.1 改进1:平衡树


连个树修改根节点时,避免修改比较高的树的根节点,例如:


对比两种合并方式的效果:

实现:需要一个额外的数组,记录这个根节点下的子元素个数,比较的时候只要比较这个值的大小来决定应该改动那个子树的根节点。

4.2 改进2:路径压缩

在循环中求解某个节点的根节点时,不要一层层找,而是直接返回其grandparent节点。代码如下

5. UNION FIND算法的应用

5.1 渗透系统

黑色块表示关闭,白色块表示开启。从顶部到下部有白色的块可以走通(不能斜着走),则认为是可渗透的,每个块是否开启时有概率的。这个是可以应用在电路系统等物理系统中的。

当格子数量N足够大的时候,这是一个相变换的问题,开启的概率P有个阈值,当格子数量P大于这个值,基本都是可渗透的,当P小于这个值则基本都是不可以渗透的。


通过计算机模拟的方式来寻求这个值。使用UF算法。

5.2 实现方法

简化成图,边长N=5

方法一:检查底部的每一个白块与顶部的任意白块是否连通(时间复杂度为O(N^2),这里使用常数时间判断是否连通)

方法二:加入两个虚拟的点,构造只有一个跟节点的情形即可,O(N)

6. 课后习题

6.1 普通习题

课后习题主要是针对三个概念,一个是quick find(找起来时常数时间,但是合并连接单元做修改代价很大O(n^2)),一个是quick union(利用路径压缩,寻找仍然为常数,但是合并连接单元只要logn时间复杂度即可);最后一个考察的概念就是在路径压缩的quick union不可能出现的树的形式(某节点的孩子节点大于等于其父节点的孩子树、回路、层数大于logN的树三种形式)

感慨下:以为自己一开始懂了。。做了题目才发现问题很多,果然还是要做做题目才知道自己是不是真会了。

6.2 编程习题

作业说明

这个编程题很棒,难度适中,不仅非常好的巩固你的知识而且对锻炼编程很有帮助。作业的提交系统非常严格,从异常处理、代码格式、性能和内存使用涵盖很全。我自己也是反复几次根据提交后反馈的意见,最终修改到能拿95分,剩余5分是因为内存超标了约20%

这里就提醒二点吧:

  1. backwash的问题主要是因为isFull方法的判断,因此在isFull方法里面进行判断时,采用一个底部不采用虚拟site的grid即可
  2. 为了方便对一个open的site的四周做连通性测试时不考虑越界问题,可以在整个原本的site加个边框,也就是原本边长为N的,实际处理时安装边长为N+2来处理

具体的代码就请看我的github吧,里面的注释已经写得非常清楚了
percolation问题源代码