Week 1 | Union-Find | Princeton Algorithms

解决算法问题的步骤：

・Model the problem.

・Find an algorithm to solve it.

・Fast enough? Fits in memory?

・If not, figure out why.

・Find a way to address the problem.

・Iterate until satisfied.

1. 问题分析

连接两个节点，且能查找两个节点是否相连。（灰色的是辅助方法）

目的：

・Number of objects N can be huge.

・Number of operations M can be huge.

2. 方法一：Quick-Find

• 算法：设置一个id数组，当id相同，说明两节点联通。在union操作时，需要将所有与id[p]相同id的节点改为id[q].

  

• 实现：

  

• 时间分析：union操作太慢。如果是N个objects，M次union操作，需要MN的时间，因为每次都遍历了整个数组。

  

3. 方法二：quick-union

• 算法：id[]的意义不再代表id，而是代表父节点。不需要再遍历数组找到与id[p]相同id的节点再更改为id[q]，而是将p节点的root节点连接到q节点的root节点上。需要增加一个辅助节点找到该节点的root节点。

  

• 实现：root方法的原理是，顺着树往上找，直到节点的id等于它本身。

  

• 时间分析：树可能变得很高，且每次find都要遍历去找root，find更慢了。

  

4. 改进1：weighting

• 算法：不再是一定将p的root连接到q的root上，而是将size小的root连接到大的root上。能够让树更矮。（因为如果大的root连接到小的root上，那么大的树中所有节点深度都+1，加深的节点会比反过来连接更多，查找花费的时间更长）

  

  

• 实现：加入一个size数组，表示以该节点为root的树有多少个节点。

  

• 时间分析：

  

  logN的证明：树的size每次增加时最多加倍，而最多加倍logN次。

  

5. 改进2：path compression

• 算法：Just after computing the root of p, set the id of each examined node to point to that root.在计算完p的root后，将每一个从p到root路径中经过的节点都连接到被计算出的root上。

  

  

• 实现：第二个实现方法实际上没有把每个p到root之间经过的节点都连接到root上，而是将每一个经过的节点都连接到其祖父节点上（这样经过的），使路径长度减半。

  

  

• 时间分析：

  

  lg*N可以被视为常数，在现实世界中再大的N它的值也不会超过5.

  WQUPC在理论上不是线性的，在实际中是线性的。

  不会有更好的算法了。

6. 应用

见PPT。渗滤系统，N*N的方格，每一个格子有p的几率是open的，1-p的几率是blocked。当p是多少的时候，这个系统几乎一定是可以渗滤（即能从第一行通到最后一行）的呢？可以通过并查集实现该系统，大量计算机实验来确定p。