union-find算法分析

背景

首先描述我们要解决的问题：问题的输入时一列证书对，其中每个整数都表示一个某种类型的对象，一对整数p q可以被理解为“p和q是相连的”。假设“相连”是一种等价关系，即：

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

这个问题也被通俗地称为动态连通性问题。

Java实现

下面就用Java来一步一步实现算法。

union-find实现

import edu.princeton.cs.algs4.StdIn;
import edu.princeton.cs.algs4.StdOut;

public class UF {
    private int[] id;        // 分量id（以触点作为索引）
    private int count;        // 分量数量

    // 初始化分量id数组
    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;
    }

    // 如果p和q存在于同一个分量中则返回true
    public boolean connected(int p, int q) {
        return find(p) == find(q);
    }

    p（0到N-1）所在的分量的标识符
    public int find(int p) {
        // nothing
    }

    // 在p和q之间添加一条连接
    public void union(int p, int q) {
        // nothing
    }

    // 解决由StdIn得到的动态连通性问题
    public static void main(String[] args) {
        int N = StdIn.readInt();        // 读取触点数量
        UF uf = new UF(N);            // 初始化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");
    }
}

quick-find算法

现在来用第一种最简单的方法实现find()和union()。只要保证当且仅当id[p]等于id[q]时p和q是连通的。即，在同一个连通分量中的所有触点在id[]中的值必须全部相同。代码如下：

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

// 将p和q归并到相同的分量中
public void union(int p, int q) {
    int pID = find(p);
    int qID = find(q);

    if(pID == qID) {
        return;     // 如果p和q已经在相同的分量之中则不需要采取任何行动
    }

    // 将p的分量重命名为q的名称
    for(int i = 0; i < id.length; i++) {
        if(id[i] == pID) {
            id[i] = qID;
        }
    }

    count--;
}

quick-union算法

上一种算法是平方级别的，不能处理大型问题。第二种算法是它的互补算法：每个触点所对应的id[]元素都是同一个分量中另一个触点的名称（也可能是它自己）————我们将这种联系称为链接。它的实现很简单：由p和q的链接分别找到它们的根触点，然后只需要将一个根触点链接到另一个即可将一个分量重命名为另一个分量。Java代码实现：

// 找出分量的名称
public int find(int p) {
    while(p != id[p]) {
        p = id[p];
    }

    return p;
}

// 将p和q的根节点统一
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算法

这一种是有质变的算法，将性能提高到对数级别。与其向上面的算法union中随意将一棵树连接到另一个树，这个算法是会记录每一棵树的大小并总是将较小的树连接到较大的树上。这项改动需要添加一个数组和一些代码来记录树中的节点数。下面是Java代码实现：

public class WeightedQuickUnionUF {
    private int[] id;        // 父链接数组（由触点索引）
    private int[] sz;         //（由触点索引的）各个根节点所对应的分量的大小
    private int count;        // 连通分量的数量

    public WeightedQuickUnionUF(int N) {
        count = N;
        id = new int[N];
        sz = new int[N];

        for (int i = 0; i < N; i++) {
            id[i] = i;
            sz[i] = 1;
        }
    }

    public int count() {
        return count;
    }

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

    // 跟随链接找到根节点
    public 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--;
    }
}

最优算法————路径压缩

这一种算法是最优的算法，接近理想情况1，方法就是在检查节点的同时将它们直接链接到根节点。实现起来也很简单，只需要为find()添加一个循环，将在路径上遇到的所有节点都直接链接到根节点。所得到的结果几乎是完全扁平化的树，它和quick-find算法理想情况下所得到的树非常接近。下面是代码实现：

public int find(int p) {
    int temp = p;

    while(p != id[p]) {
        p = id[p];
    }

    while(temp != id[p]) {
        int tempId = id[temp];
        id[temp] = id[p];
        temp = tempId;
    }

    return p;
}

总结

总结一下研究算法问题的基本步骤：

完整而详细地定义问题，找出解决问题所必需的基本抽象操作并定义一份API。
简洁地实现一种初级算法，给出一个精心组织的开发用例并使用实际数据作为输入。
当实现所能解决的问题的最大规模达不到期望时决定改进还是放弃。
逐步改进实现，通过经验性分析或（和）数学分析验证改进后的效果。
用更高层次的抽象表示数据结构或算法来设计更高级的改进版本。
如果可能尽量为最坏情况下的性能提供保证，但在处理普通数据时也要有良好的性能。
在适当的时候将更细致的深入研究留给有经验的研究者并继续解决下一个问题。