并查集

动态连通性问题的输入为一列整数对，其中每个整数都表示一个某种类型的对象，一对整数 p 、 q 可以被理解为“ p 和 q 是相连的“。

可使用 并查集 来滤掉序列中所有无意义的整数对(两个整数均来自同一个等价类中)。换句话说，当程序从输入中读取了整数对 p 、 q 时，如果已知的所有整数对都不能说明 p 和 q 是相连的，那么则将这一对整数输出并相连；如果两者已相连，则忽略这对整数。

API

public class UF

quick-find算法

原理

保证当且仅当 id[p] 等于 id[q] 时 p 和 q 是连通的，即同一个连通分量中的所有触点在 id[] 中的值必须相同。

所以find()方法中可以直接返回 p 的连通分量号，而union()方法则需要首先判断两个点是否在同一个连通分量中，如果在就不采取任何行动，不在就把所有id与p的id相同的点的id都改为q的id，即将两个分量连起来，消除一个分量。

图示

union()图示

总过程

代码

public class UF {
    private int[] id;   //分量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);
    }
    //返回点p的连通分量编号
    public int find(int p) {
        return id[p];
    }
    //将两个点连通在一起
    public void union(int p, int q) {
        int pID = id[p];
        int qID = id[q];
        if (pID == qID) return;
        for (int i = 0; i < id.length; i++)
            //将所有id为pID的点的id都改为qID，消除一个分量
            if (id[i] == pID)   id[i] = qID;
        count--;
    }
}

复杂度

$O(N^2)$

find()访问数组为 $O(1)$ ，union()访问数组为 $O(N)$ ，假设最后只得到了一个连通分量，那么至少要调用 $N-1$ 次union()，所以总的时间复杂度为 $O(N^2)$ 。

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S1_foundation/S1_5_Union_Find/Quick_Find

quick-union算法

原理

每个触点所对应的 id[] 元素是同一个分量中的另一个触点，也可能是它自己(与quick-find不同)，将这种联系称为链接。

在实现find()方法时，从给定的触点开始，由它的链接得到另一个触点，再由这个触点的链接达到第三个触点，如此继续直到到达一个根触点，即链接指向自己的触点。当且仅当分别由两个触点开始的这个过程到达了同一个根触点时它们存在于同一个连通分量。

union()方法中，由 p 和 q 的链接分别找到它们的根触点，然后只需将一个根触点连接到另一个即可将一个分量重命名为另一个分量。

图示

find()和union()图示

总过程

代码

public class UF {
    private int[] id;   //id[触电]=另一连通根触电（与quick_find中不同）
    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);
    }
    //返回点p的连通分量编号
    public 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-union算法比quick-find算法更快，因为它不需要为每对输入遍历整个数组。

但它在最坏情况下复杂度仍为 $O(N^2)$ 。

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S1_foundation/S1_5_Union_Find/Quick_Union

加权quick-union算法

原理

在quick-union算法的基础上，记录每一棵树的大小，并总是将较小的树连接到较大的树上。

图示

代码

public class WeightedQuickUnionUF {
    private int[] id;   //id[触点]=另一连通根触点（与quick_find中不同）
    private int[] sz;   //（由触点索引的）各个根结点所对应的分量大小
    private int count;  //连通分量的数量
    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
        sz = new int[N];
        for (int i = 0; i < N; i++)
            sz[i] = 1;
    }
    public int count() {
        return count;
    }
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }
    private int find(int p) {
        //跟随链接找到根结点
        while (p != id[p])  p = id[p];
        return p;
    }
    public void union(int p, int q) {
        int i = find(p);
        int j = find(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];
        }
        count--;
    }
}

复杂度

处理 $N$ 个触点和 $M$ 条链接的时间复杂度为 $O(MlogN)$

源代码

https://github.com/XutongLi/Algorithm-Learn/tree/master/src/S1_foundation/S1_5_Union_Find/Weighted_Quick_Union

各种并查集算法性能特点

与DFS求连通性比较

理论上DFS 更快，因为时间复杂度为常数。

但实际上使用并查集更快，因为它是一种动态算法，不需要完整地构造一幅图，在任何时候都可以用接近常数的时间检查两个顶点是否连通。

在完成只需要判断连通性或是需要有大量连通性查询和插入操作混合等类似的任务时一般使用并查集；DFS更适合实现图的抽象数据类型。

本博客采用 CC BY-NC-SA 3.0 许可协议。转载请注明出处！ 本文链接： http://brianleelxt.top/2018/09/08/Union_Find/