背景

对于一个无向图，我们希望判断两个节点之间是否是连通的，或者说，从点p到点q，是否存在一条路径。想要在大规模的图中快速判断两点是否连通，显然并不容易。

应用的场景

这里的节点可以代表很多具体的应用：

1. 数字图片中的像素

2. 在网络中的计算机

3. 在社交网络上的用户

4. 芯片上的晶体管

5. 集合中的元素

6. 程序的变量名

并查集API

并查集是一种树型的数据结构，用于处理一些不相交的集合的合并和查询问题。我们的并查集提高一下几个接口。

UF(int N): 并查集的构造函数

void union(int p, int q): 将两个节点连接的函数

boolean connected(int p, int q): 判断两个节点是否连接

int find(int p)与int count()这两个函数的作用后续会讲到。

Quick-Find

这种方式思路十分简单和清晰，维护一个id数组，其中相连接的元素有一样的值，代码如下：

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;
 }
}

这种方式的缺点很明显，在进行union操作的时候需要改变很多值，复杂度为O(n)，效率不够高。

QuickUnion(Lazy Approach)

id数组中的值对应的是节点的父节点的值。

代码如下：

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 (i != id[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;
     }
}

同样，这种方法效率也不高，因为没有对建树的方式加以规定，很可能出现深度特别大的树。

Union-Find

对于Quick-Union方法，我们做如下改进：

(1) Weighted Tree

由下图可知，通过上述方式，我们大大减少了图的深度。

(2) Path Compress

如下图所示：

在该图中，9节点是和根节点0相连接的，我们完全可以把9节点直接连到0节点上，而不会对我们的函数造成任何结果上的影响。通过这种方式，我们也可以大大减少树的深度。同时，这种方法在代码上的实现极其简单，只需要把对应节点的父节点设为父节点的父节点就可以了。

应用

在普林斯顿的算法课程中，介绍到了一种渗透模型，如下图所示。

可以这样理解，白色代表空洞，而黑色代表不透水的墙面，水从上而下流动，蓝色代表的是水可以流到的地方，目标是判断在给定空洞和墙面分布的基础上，判断水是否能从顶层流到底部。

这个题目是并查集的十分直接的应用，利用上面讲到的知识，我们可以很容易的建模，找到解决问题的思路，但是在细节上，可能还要有一些要斟酌的成分。

代码在我的github中：https://github.com/caozixuan/AlgorithmLearning