并查集（Union-Find）

并查集是算法4介绍的第一个算法，我觉得很有意思，理解起来也不难。它主要是解决图论中「动态连通性」问题的。

此算法主要有两个操作，connected是返回两个元素是否连通，union是合并两个连通的元素集合。

首先用数组来表示，同一个集合的元素的值是相同的，如果合并集合，则需要修改某一集合的所有元素的值，查询是否属于同一个集合只需要比较值是否相等即可。图示如下：

image.png

代码表示如下：




public class Union_Find {
private int[] id;
//初始化数组
public Union_Find(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 - 1; i++ ) {
if(id[i] == pid)
id[i] = qid;
}
}
}

上述代码的合并集合时需要多次修改数组的元素，如果改用树来表示就可以节省很多的修改次数。也是用一个一维数组。假设每个节点都指向它的父节点，根节点指向本身。一开始每个节点都是根节点，合并只需要把一个集合的根节点指向另一个集合的根节点就可以。判断是否同一个集合只要比较根节点是否相等即可。图示如下：

代码实现如下：


public class QuickFindUF {
private int[] id;
//初始化
public QuickFindUF(int N) {
for(int i = 0; i < N; i++) {
id[i] = i;
}
}

//寻找根节点
int root(int i) {
while(id[i] != i) {
i = id[i];
}
return i;
}

//判断是否两个元素是否连通

boolean connected(int p, int q) {
return root(p) == root(q);
}

//连通两个图
void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
id[rootP] = rootQ;
}
}

因为是树的结构，如果树不平衡，最差的情况会退化成链表，所有需要进行一些优化。

优化一：增加size数组，记录树的权重，令小树总是指向大树。


void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if(rootP == rootQ) return;
//令小树指向大树
if(size[rootP] <= size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}

优化二：可以在选在根节点的时候展平树，只需要加一句代码：

int root(int i) {
while(id[i] != i) {
//展平树
id[i] = id[id[i]];
i = id[i];
}
return i;
}

完整代码如下:

public class QuickFindUF {
    private int[] id;
    //初始化
    private int[] size;
    public QuickFindUF(int N) {
        for(int i = 0; i < N; i++) {
            id[i] = i;
            size[i]  = 1;
        }
    }
    
    int root(int i) {
        while(id[i] != i) {
            id[i] = id[id[i]];
            i = id[i];
        } 
        return i;
    }
    
    boolean connected(int p, int q) {
        
        return root(p) == root(q);
    }
    
    void union(int p, int q) {
        int rootP = root(p);
        int rootQ = root(q);
        if(rootP == rootQ) return;
        //令小树指向大树
        if(size[rootP] <= size[rootQ]) {
            id[rootP] = rootQ;
            size[rootQ] += size[rootP];
        }
        else {
            id[rootQ] = rootP;
            size[rootP] += size[rootQ];
            
        }
    }

}