union-find算法

问题描述

动态连通性

问题的输入是一列整数对，其中每个整数都表示一个某种类型的对象，一对整数p和q可以被理解为”p和q是相连的“。假设”相连“是一种等价关系，意味着具有：

• 自反性：p和p是相连的；
• 对称性：如果p和q是相连的，那么q和p也是相连的；
• 传递性：如果p和q是相连的且q和r是相连的，那么p和r也是相连的。

等价关系能够将对象分为多个等价类。在这里，当且仅当两个对象相连时它们才属于同一等价类。我们的目标是编写一个程序来过滤掉序列中所有无意义的整数对。换句话说，当程序从输入中读取了整数对p q时，如果已知的所有整数对都不能说明p和q是相连的，那么则将这一对整数写入到输出中。如果已知的数据可以说明p和q是相连的，那么程序应该忽略p q这对整数并继续处理输入中的下一对整数。如图：

为了达到期望的效果，我们需要设计一个数据结构来保存程序已知的所有整数对的足够多的信息，并用它们来判断一对新对象是否相连的。我们将这个问题通俗地叫做动态连通性问题。

术语

使用网络方面的术语，将对象称为触点，将整数对称为连接，将等价类称为连通分量或是简称分量。简单起见，假设我们有用0到N-1的整数所表示的N个触点。

算法设计

算法API

API	功能
UF(int N)	以整数标识（0到N-1）初始化N个触点
void union(int p, int q)	在p和q之间添加一条连接
int find(int p)	p（0到N-1）所在的分量的标识符
boolean connected(int p, int q)	如果p和q存在于同一个分量中则返回true
int count()	连通分量的数量

quick-find的实现

API已经说明触点和分量都会用int值表示，所以我们可以用一个以触点的名称作为分量的标识符，因此你可以认为每个分量都是由它的触点之一表示的。
这种方法是保证当且仅当id[p]等于id[q]时p和q是连通的。换句话说，在同一个连通分量中的所有触点在id[]中的值必须全部相同。
如图是开发用例在处理测试数据的轨迹：

package section1_5;

public class UFOfQuickFind {
    private int[] id;
    private int count;

    public UFOfQuickFind(int N) {
        count = N;
        id = new int[N];
        for (int i=0;i<N;i++) {
            id[i] = i;
        }
    }

    public int count() { return count; }

    public int find(int p) { return id[p]; }

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

    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 = 10;
        UFOfQuickFind uf = new UFOfQuickFind(N);
        int[][] data = new int[][]{{4,3},{3,8},{6,5},{9,4},{2,1},{8,9},{5,0},{7,2},{6,1},{1,0},{6,7}};
        int idx = 0;
        while(idx<data.length) {
            int p = data[idx][0];
            int q = data[idx][1];
            if (uf.connected(p,q)) {
                idx++;
                continue;
            }
            uf.union(p,q);
            idx++;
            System.out.println(p+" "+q);
        }
        System.out.println(uf.count()+"components");
        for (int i=0;i<uf.id.length;i++) {
            System.out.print(uf.id[i]+" ");
        }
    }
}

输出：

quick-union的实现

这种方法可以提高union()方法的速度。每个触点所对应的id[]元素都是同一分量中另一触点的名称（也可能是它自己）——我们将这种联系称为链接。在实现find()方法时，我们从给定的触点开始，由它的链接得到另一个触点，再由这个触点的链接到达第三个触点，如此继续跟随着链接直到到达一个根触点，即链接指向自己的触点。当且仅当分别由两个触点开始的这个过程到达了同一个根触点时它们存在于同一个连通分量之中。如图：

package section1_5;

public class UFOfQuickUnion {
    private int id[];
    private int count;

    public UFOfQuickUnion(int N) {
        count = N;
        id = new int[N];
        for (int i=0;i<N;i++) {
            id[i] = i;
        }
    }

    public int count() {
        return count;
    }

    public int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

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

    public void union(int p, int q) {
        int pROOT = find(p);
        int qROOT = find(q);

        if (pROOT == qROOT) return;
        id[pROOT] = qROOT;
        count--;
    }

    public static void main(String[] args) {
        int N = 10;
        UFOfQuickUnion uf = new UFOfQuickUnion(N);
        int[][] data = new int[][]{{4,3},{3,8},{6,5},{9,4},{2,1},{8,9},{5,0},{7,2},{6,1},{1,0},{6,7}};
        int idx = 0;
        while(idx<data.length) {
            int p = data[idx][0];
            int q = data[idx][1];
            if (uf.connected(p,q)) {
                idx++;
                continue;
            }
            uf.union(p,q);
            idx++;
            System.out.println(p+" "+q);
        }
        System.out.println(uf.count()+"components");
        for (int i=0;i<uf.id.length;i++) {
            System.out.print(uf.id[i]+" ");
        }
    }
}

输出：

加权quick-union的实现

与其在union()中随意将一棵树连接到另一棵树，我们现在会记录每一棵树的大小并总是将较小的树连接到较大的树上。这项改动需要添加一个数组和一些代码来记录树中的节点数，但它能够大大改进算法的效率。该算法构造的树的高度也远远小于未加权所构造的树的高度。如图：

package section1_5;

public class UFOfQuickUnionwithweight {
    private int id[];
    private int count;
    private int sz[];

    public UFOfQuickUnionwithweight(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 int find(int p) {
        while (p != id[p]) {
            p = id[p];
        }
        return p;
    }

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

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

    public static void main(String[] args) {
        int N = 10;
        UFOfQuickUnionwithweight uf = new UFOfQuickUnionwithweight(N);
        int[][] data = new int[][]{{4,3},{3,8},{6,5},{9,4},{2,1},{8,9},{5,0},{7,2},{6,1},{1,0},{6,7}};
        int idx = 0;
        while(idx<data.length) {
            int p = data[idx][0];
            int q = data[idx][1];
            if (uf.connected(p,q)) {
                idx++;
                continue;
            }
            uf.union(p,q);
            idx++;
            System.out.println(p+" "+q);
        }
        System.out.println(uf.count()+"components");
        for (int i=0;i<uf.id.length;i++) {
            System.out.print(uf.id[i]+" ");
        }
    }
}

输出：

算法分析

quick-find

find()操作的速度显然是很快的，因为它只需要访问id[]数组一次。但quick–find算法一般无法处理大型问题，因为对于每一对输入union()都需要扫描整个id[]数组。
quick-find算法的运行时间对于最终只能得到少数连通分量的一般应用是平方级别的。

quick-union

分析quick-union算法的成本依赖于输入的特点。在最好情况下，find()只需要访问数组一次就能够得到一个触点所在的分量的标识符；而在最坏情况下，这需要2N+1次数组访问。由此我们不难构造一个最佳情况的输入使得解决动态连通性问题的用例的运行时间是线性级别；另一方面，我们也可以构造一个最坏情况的输入，此时它的运行时间是平方级别的。
目前，我们可以将quick-union算法看做是quick-find算法的一种改良，因为它解决了quick-find算法中最主要的问题（union()操作总总是线性级别的）。

加权quick-union

对于N个触点，加权quick-union算法构造的森林中的任意节点的深度最多为lgN，所以对于动态连通性问题，加权quick-union算法是三种算法中唯一可以用于解决大型实际问题的算法。加权quick-union算法处理N个触点和M条连接时最多访问数组cMlgN次，其中c为常数。这个结果和quick-find算法需要访问数组至少MN次形成了鲜明的对比。因此，有了加权quick-union算法我们就能保证能够在合理时间范围内解决实际中的大规模动态连通性问题。

本文地址：https://blog.csdn.net/qq_41242680/article/details/110203876