Union-Find算法(Java)

发表于 | 更新于: | 分类于
本文主要介绍Union-Find算法，它主要是用来验证一个数据对是否连通。

最近开始看《算法》第四版，于是想对其中感兴趣和有用的算法进行总结，一方面可以锻炼自己总结的能力，另一方面可以在总结中加深对算法的理解，以方便自己以后对这些常用的算法进行回顾以及学习。
今天要谈的是Union-Find算法，从名字中就能看出这个算法主要包括两个部分，分别是union和find。那么它们究竟是什么意思呢？
其实这主要是解决的一个连接性问题，就是在一堆数据中判断给定的数据对是否连通，如果这个数据对已经连通则不在这对数据之间建立直接通路，否则在两个数据之间建立通路。这个算法可以用来解决网络通信中两个点之间的通信是否存在的问题，那么有关这个算法，我给出两种参考方法。
前提：
已经创建一个数组，并对其中的值按照0到N的顺序赋值。
方法一：
quick-find

1
2
3
4
5
6
7
8
9
10
11
12
13
public int find(int p){
    return id[p];
}
public void union(int p,int q){
    int pID = find(p);
    int qID = find(q);
    if(pID==qID)
        return;
    for(int i=0;i<id.length;i++)
        if(id[i]==pID)
            id[i]=qID;
    count--;
}

上面的代码主要给出了两个重要的函数，一个是find，一个是union，其中find直接返回数字在数组中的值，而union中则首先对数据对进行检查，如果他们的值相同则忽略这对数据，否则比较查找出来的值是否与id[i]相同，如果相同则将qID赋予id[i]作为标记，表示这个数据对所对应的值已经相同。
e.g.
IZsJ3.png
之后的其余数据都可以按照上述方式进行模拟，总体思想就是通过find找到数据对中的数所对应的数值，如果不同则循环查找，如果有id[i]的值与find函数返回的值相同，则将qID的值赋予id[i]，表示数据对值相同，这样就可以通过相同值的方法判断两个数据是否在同一个集合中。
不过这个方法有一个明显的缺陷，那就是每次查找时都需要遍历整个数组，这在数据量较大的情况下性能会有很大的影响，所以引出了方法二。
方法二：
quick-union

1
2
3
4
5
6
7
8
9
10
11
12
13
private int find(int p){
    while(p!=id[p])
        p=id[p];
    return p;
}
public void union(int p,int q){
    int pRoot = find(p);
    int qRoot = find(q);
    if(pRoot==qRoot)
        return;
    id[pRoot]=qRoot;
    count--;
}

该方法与quick-find的主要区别在于find方法，在quick-union中采用了自循环的方式对访问过的值进行修改，这样的好处就是可以通过对数组的直接访问最终一定会找到根结点，从而通过根结点的比较快速判断数据对是否位于同一集合。这个方法的关键在于find函数的使用，这其中使用while就是为了通过自身的“追根溯源“进行查找。
IZu6K.jpg
可以配合上图对quick-union的查找过程进行模拟，相信几个回合下来就能清楚掌握。
最后放出完整代码

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
33
34
35
36
37
38
39
40
41
42
43
44
45
public class UF {
    private int[] id;
    private int count;
    public UF(int N){
        count = N;
        id = new int[N];
        for(int i = 0;i<N;i++)
            id[i]=i;
    }
    public int count(){
        return count;
    }
    public boolean connected(int p,int q){
        return find(p)==find(q);
    }
    //此处采用quick-find方法，可以自行替换为quick-union方法
    public int find(int p){
        return id[p];
    }
    public void union(int p,int q){
        int pID = find(p);
        int qID = find(q);
        if(pID==qID)
            return;
        for(int i=0;i<id.length;i++){
            if(id[i]==pID)
                id[i]=qID;
        }
        count--;
    }

    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))
                continue;
            uf.union(p,q);
            StdOut.println(p+" "+q);
        }
        StdOut.println(uf.count+"components");
    }
}

这其中的StdOut以及StdIn库使用自algs4这个jar包，下载地址：
https://algs4.cs.princeton.edu/code/algs4.jar