【学习】并查集

采用princton的Coursera课程：algorithms1&2

union-find:

  • dynamic connecticity
  • quick find
  • quck union
  • improvemnts
  • applications

动态连通性

union commamd指令: 连接两个对象
find/connected query指令： 检查是否有两个对象连通的路径

应用场景：在编程时，将整数作为数组的索引时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

//以下使用algs4。jar包
public static void main(String[] args)
{
 int N = StdIn.readInt();
 UF uf = new UF(N);
 while (!StdIn.isEmpty())
 {
 int p = StdIn.readInt();
 int q = StdIn.readInt();
 if (!uf.connected(p, q))
 {
 uf.union(p, q);
 StdOut.println(p + " " + q);
 }
 }
}

快速查找(Quick-find)

java实现方式

数据结构：

  • 长度为N的整数数组 id[]
  • 当且仅当p和q的id值相同，表示p和q连通
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    public class QuickFind{
        private int[] id;
        public QuickFind(int N){
            id=new int[N];
            for(int i=0;i<N;i++){
                id[i]=i;
            }
        }
        public boolean connected(int p,int q){
            return id[p]==id[q];
        }
        public void Union(int p,int q){
            int pid=id[p];
            int qid=id[q];
            for(int i=0;i<id.length;i++){
                if(id[i]==pid){
                    id[i]=qid;
                }

            }
        }

    }

    算法分析：

    快速查找too slow？
  • cost model: 初始化、union都需要遍历整个数组，复杂度正比于N；查找很快,复杂度为常数
  • union太expensive:N**2的复杂度

快速并集（Quick-union [lazy approach]）

数据结构：树型

  • 长度为N的整数数组 id[]
  • id[i]时id的父节点
  • i的root节点为id[id[id[…id[i]…]]]

对象连通? 判断p和q的根节点是否相同

集合：当连接两个对象p,q，设置p的根节点为q根节点的id

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public class QucikUnion{
    private int[] id;
    public QucikUnion(int N){
        id=new int[N];
        for(int i=0;i<N;i++){
            id[i]=i;
        }

    }
    private int root(int i){
        while(id[i]!=i){
            i=id[i];
        }
        return i;
    }
    public boolean connected(int p,int q){
        return root(p)==root(q);

    }
    public void union(int p,int q){
        id[root(p)]=id[root(q)];
    }


}

然而quick-union算法也无法适应大规模数据
cost model:

algorithminitializeunionfind
quick-findNN1
quick-unionNN(包含找根节点)N

我们对比快速查找和快速并集，不难发现各自的缺陷

快速查找:

  • 并集费时（N）
  • 树是平展的，但维持平铺的状态需要费时（怎么理解？）

快速并集：

  • 树高
  • 查找费时（N）

所以，我们接下来对并查做一些改进。

加权快速并集（Weighted quick-union）和压缩路径快速并集(Quick union with path compression)

我们跟踪记录生成树的大小（包含对象的个数），将其作为权。并集的时候，权轻的树根节点改为权重的根节点。换句话说，就是小树接到大树下，而非前树接到后树下。这样降低所有节点到根节点的平均距离，并且避免树过深的的算法叫加权快速并查

加权快速并查

数据结构：与快速查找相同，增加sz[i]存储以i为根节点的树的大小（树下包含对象的数量）

并集：小树接到大树下，实时更新sz[i]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
public class QucikUnion{
    private int[] id;
    public QucikUnion(int N){
        id=new int[N];
        for(int i=0;i<N;i++){
            id[i]=i;
        }

    }
    private int root(int i){
        while(id[i]!=i){
            i=id[i];
        }
        return i;
    }
    public boolean connected(int p,int q){
        return root(p)==root(q);

    }
    public void union(int p,int q){
        if(sz[p]>sz[q])
          {id[root(q)]=root(p);
          sz[p]+=sz[q];
          }
        else
          {id[root(p)]=root(q);
          sz[q]+=sz[p];
          }
    }


}

算法分析：

1.运行时间的分析：

  • 查找：时间和p、q的深度成正比
  • 并集：时间为常量

2.任意节点X最大为lgN

以下为简答的数学证明（注意：在计算机领域，lgN底数为2）：

  1. 定义：令(N)表示节点总数，(T_i)表示进行了(i)次并集操作后的某个树的大小（节点数），(h_i)表示这个树的高度（即树中任意节点的最大深度）。

  2. 观察：在加权快速并集中，每次并集操作都是将一个较小的树连接到一个较大的树上。因此，每次树的大小至少翻倍（对原先的小树而言）。

  3. 数学归纳：

    • 基础情况：当树大小(T = 1)时，高度(h = 0)，满足(h \leq \lg T)。
    • 归纳步骤：假设对于树的大小为(Tk)时，其高度(h_k \leq \lg T_k)成立。当执行一次并集操作，将一个大小至少为(T_k)的树连接到另一个大小至少为(T_k)的树上时，结果树的大小至少为(2T_k)，因此新树的高度(h{k+1} = h_k + 1)（因为最多增加一层）。

  4. 证明：根据归纳步骤，新的高度(h{k+1} \leq \lg T_k + 1 = \lg (2T_k)(完全二叉树时) = \lg T{k+1})。这证明了在任意时刻，树的高度（深度）(h)总是小于等于(\lg N)，其中(N)是节点总数。

结论

因此，我们可以得出结论，在加权快速并集算法中，任何节点(x)的深度最大为(\lg N)。这个性质保证了查找操作的高效性，因为查找路径长度的上限是对数级别的。

algorithminitializeunionfind
quick-findNN1
quick-unionNN(包含找根节点)N
weightedNlgN(包含找根节点)lgN

我们还可以进一步优化

路径压缩快速并集

在快速并集时，在找到根节点时，将之前的检查点重新直接指向根节点，这样压缩了之后的检查路径的算法叫路径压缩快速并集（Quick union with path compression）

java实现方式

1
2
3
4
5
6
7
8
...
private int root(int i){
    while(id[i]!=i){
        id[i]=id[id[i]];
        i=id[i];
    }
    return i;
}

但还可以进一步优化算法。

集大成的玩意儿

怎么优化呢？

很简单，加权和路径压缩搅一块儿就好啦。所以诞生了这么个玩意儿。
Weighted quick-union with path compression!!

接下来简单介绍对其平摊分析

平摊分析（Amortized analysis）

Q:什么是平摊分析？
A:是用于算法分析的方法。在使用平摊分析前须知道数据结构各种操作所可能发生的时间，并计算出最坏情况下的操作情况并加以平均。能够确认最坏情况性能的每次操作耗费的平均时间，但不能确认平均情况性能。（from wikipedia）

1.Hopcroft-Ulman, Tarjan 提出：从一个空的数据结构开始，对N个对象执行M次并查集操作（包括查找和合并）最多需要 c(N + M \lg N) 次数组访问。其中，lg N 是迭代对数函数，表示需要多少次迭代对数运算才能使N减少到1以下。这是一个增长非常缓慢的函数，对于所有实际的N值，lg^ N 都是一个非常小的常数。如下：

  • 当 N = 1 时，lg^* N = 0
  • 当 N = 2 时，lg^* N = 1
  • 当 N 增加到16时，lg^* N = 3
  • 直到 N = 65536 时，lg^* N 才变成4

2.分析可以进一步改进为 N + M \alpha(M, N)，其中 alpha(M, N) 是阿克曼函数的逆函数，也是一个非常慢增长的函数。这表明在实际应用中，加权快速合并算法（Weighted Quick-Union）配合路径压缩（Path Compression，简称WQUPC）的性能非常接近线性时间。

3.线性时间算法问题：对于M次并查集操作在N个对象上，是否存在线性时间算法？理论上，基于加权快速合并与路径压缩的分析（WQUPC），并不是严格的线性时间。

  • 然而，实际上，这个算法的性能非常接近线性时间，考虑到数据输入的成本，其代价在常数因子范围内。

Amazing Fact

！！

  • Fredman-Saks 提出的惊人事实：不存在严格的线性时间算法。即便是WQUPC算法，也不能在理论上达到完全的线性时间复杂度。

WQUPC

WQUPC通过维护子树大小并在执行查找操作时压缩路径来优化合并操作，使得后续的查找操作更高效。通过这种方式，算法的平均时间复杂度非常接近线性，尽管在最坏情况下并非完全线性，但在实际应用中表现出色。

总结

algorithmworst-case time
quick-findM N
weighted QUM N
weighted QUN + M log N
QU+compressionN + M log N
WQUPCN+ M lg*N

事实证明，超级计算机靠暴力无法解决的，超级算法可以

应用场景

大致应用场景直接抄PPT上的内容了，这块主要讲的是渗流问题

  • 渗流
  • 游戏（围棋，Hex）
  • 动态连通性
  • 最小公共祖先
  • 有限状态自动机的等价性
  • 物理中的Hoshen-Kopelman算法
  • Hinley-Milner多态类型推断
  • Kruskal’s最小生成树算法
  • Fortran中编译等价语句
  • 形态学属性的开启和关闭
  • 图像处理中Matlab的bwlabel()函数

渗流问题Coursera留了一个大作业，下篇具体写

全篇总结

并查集主要解决的是动态连通性问题，为了优化算法引入了树模型作为对象连通结构。那么普通的quick-union在面临大规模数据可能遇到两个问题：树过高，路径过长；于是我们分别用加权和路径压缩算法加以解决，最后尝试将加权和路径压缩搅在一起成了本集顶级战力WQUPC。

接下来要滚去写大作业力