并查集

1.dynamic connectivity

首先我们考虑如图所示的问题，在图中我们可以看到执行所有的操作后得到最终结果，由于执行过程中我们可以动态加入连通分量，所以称之为动态连通。 上图中的结果可以容易得到，但当图中节点数量增大时，我们需要程序辅助判断。我们现在给出几个比较明显的假设，首先，每个节点p都链接到p本身；其次，如果p连接到q，则q也连接到p；最后，如果p连接到q，q连接到r，则p也连接到r。 将互相连接的节点视为一个集合，如果两个节点同时存在于同一个集合之中则可以确定两点之间连通，即初始化的空图为n个single set，每次执行一次union操作相当于将集合合并，这样对于节点之间是否连接我们可以给出一个判断。 下面给出UF的API：

public class UF
________________________________________________________
UF(int N) 初始化并查集数据结构中的n个对象
void union（int p，int q） 在p和q之间连接
boolean connected（int p，int q） 判断pq是否连通
int find（int p） 在0到n-1中寻找与p相等的值
int count（） 计数

下面给出调用UF的一个列子：

import main.java.edu.princeton.cs.algs4.*;
public class Main{
    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);
            }
        }
    }
}

2.quick-find

下面考虑如何实现并查集的数据结构，将各个点视为一个数组，将数组中所存值视为该组节点的共同标志。每次union的操作都会将两个待合并子集的标志合并，即数组中保存的值修改为同一值。 下面给出Quick-Find的Java代码实现：

import main.java.edu.princeton.cs.algs4.*;

public class QuickFindUF {
private int[] id;
public QuickFindUF(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;
}

}

但是我们可以发现Quick—Find算法对于数据较大的情况表现不好，初始化需要n步操作，union操作需要n步操作，寻找需要一次操作。这将会需要n^2操作去执行n个对象的合并操作。

3.quick-union

Linus 说过“坏的程序员担心他们的代码，而好的程序员则担心他们的数据结构及它们之间的关系。下面我们考虑一种更为合理的数据结构来表示节点之间的关系。 首先将节点之间的连接化为一颗树，这样节点之间就具有了一种全新的数据结构，将每个节点的父节点位置储存在数组中，这样id【i】 的值即为其父节点，而节点i的根节点的值是id[id[id[…id[i]…]]]. 这时判断节点是否连通的条件是它们是否拥有同一个父节点。而union操作则是将该树的根节点成为另一颗树的子节点。 下面给出Quick-Union的java实现：

import main.java.edu.princeton.cs.algs4.*;

public class QuickUnionUf {
    private int\[\] id;

    public QuickUnionUf(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){
        int i= root(p);
        int j= root(q);
        id\[i\] = j;
    }
}

这样依然存在问题，在Quick-Find算法中树太过平面，union操作太昂贵，而在Quick——Union算法中树变得过于高，union操作的最坏情况是n，而find操作太过昂贵。

4.解决办法

4.1带权

带权的方法仍然采用quick-Union算法的思想不过在带权（weighting）中我们总是将较小的树放在较高的树下面，即总是将较小树的根节点修改为较高树的子节点。 我们再来比较一下两种方法产生的树 明显带权算法产生的树更加扁平。 下面给出带权算法的java实现：

import main.java.edu.princeton.cs.algs4.*;

public class QuickUnionUf {
    private int\[\] id;
    private int\[\] sz;

    public QuickUnionUf(int N){
        id =new int \[N\];
        for(int i=0;i<N;i++) {
            id\[i\] = i;
            sz\[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){
        int i= root(p);
        int j= root(q);
        if(i==j) return;
        if(sz\[i\]<sz\[j\]){ id\[i\]=j; sz\[j\]+=sz\[i\];}
        else {id\[j\] = i; sz\[i\]+=sz\[j\];}
    }
}

分析带权算法我们发现find操作需要的时间与p和q的深度成正比，union操作则需要常数时间， 还可以发现每个节点的深度一定小于lgN。 那么为什么任意节点x的深度最多是N以2为底的对数呢？ 理解这个问题的关键在于观察节点的深度到底是在何时增加的 何时它在树中变得更深？ 当x所在的树，即图中的T1，与另一棵树，即图中的T2，合并的时候x的深度加1 好，之前我们说过只有在T2的大小 T2的大小大于等于T1的大小时才会发生这种情况 所以当x深度增加时 树的大小至少翻倍。这很关键，因为这意味着 包含x的树的大小最多可以翻N次倍因为如果从1开始 翻倍lg N次，就会得到N，而最后树中总共只有N个节点 这就是任意节点x的深度最多是N以2为底的对数的粗略证明 这对于这个算法的性能有着巨大的影响 现在，除了初始化总是需要正比于N的时间，合并和 “是否连接”或查询操作需要的时间都是正比于N以2为底的对数 这个算法能成比例适应大规模问题。当N从1百万变为10亿 花费的时间从20变为30，这就比较能接受了。

4.2路径压缩

我们想办法进一步提高程序的性能。 经过路径压缩之后树变得扁平 实现路径压缩只需在root方法中添加一行代码即可：

private int root(int i){
    while(id\[i\]!= i){
      _ **id\[i\]=id\[id\[i\]\];**_
        i = id\[i\];
    }
    return i;
}

这样我们便实现了路径压缩。合并起来即为WQUPC算法。 Hopcroft Ulman和Tarjan证明了如果 有N个对象，M个合并与查找操作的任意序列，需要访问数组 最多c(N + M lg* N)次。lg* N是个挺有意思的函数 它是使N变为1需要取对数的次数 它叫做迭代对数函数。在真实世界中 可以认为是一个小于5的数，因为lg（2^65536）=5 所以，这说明带路径压缩的带权快速合并算法 在真实世界中的时间复杂度是线性的，而实际上可以改进到 一个更有意思的函数，Ackermann函数，这个函数增长速度 比 lg 还慢。另外一点要说明的是看起来这个算法的时间复杂度已经非常接近与N成正比的线性了 它与N乘一个关于N的增长非常缓慢的函数成正比。

5.并查集的应用

・Percolation. ・Games (Go, Hex). ✓ Dynamic connectivity. ・Least common ancestor. ・Equivalence of finite state automata. ・Hoshen-Kopelman algorithm in physics. ・Hinley-Milner polymorphic type inference. ・Kruskal’s minimum spanning tree algorithm. ・Compiling equivalence statements in Fortran. ・Morphological attribute openings and closings. ・Matlab’s bwlabel() function in image processing. 下面考虑一个问题：渗透（Percolation） 给出问题的描述：1.有一个n×n的方格；2.每个方格开放的概率是p（闭合的概率是1-p）；3.一个系统称为可渗透的是顶层和底层被开放空格所连接。 ・p > p: 系统极有可能是是渗透的 ・p < p: 系统几乎不可能是渗透的； 如何判断方格之间是否连通呢？我们将每个方格考虑成一个节点 节点之间的连通性可以用连接先表示，而系统是否连通可以加入两个虚拟点，如果这两点连通即可推出系统渗透。我们要运行的就是所谓的蒙特卡罗仿真 首先将整个网格初始化为闭合的，全是黑色的，然后随机加上开放的位 每次加上一个开放位后，检查 是否使系统变得渗滤的。持续这个过程直到 系统变得是渗滤的。我们可以证明系统变得渗滤时开放位的比例 是要求的阈值的估计。我们要做的是 将这个实验运行上百万次，这我们可以在计算机上完成 只要我们能够高效地计算当前系统是否渗滤 这就是蒙特卡罗仿真，这个计算问题 为这个尚无人知道如何求解的科学或者数学问题给出的解决办法。 [gallery ids=”49,50” type=”rectangular”]