union-find算法

Union-Find算法

基本介绍

可以想象一张地图上有很多点，有些点之间是有道路相互联通的，而有些点则没有。如果我们现在要从点A走向点B，那么一个关键的问题就是判断我们能否从A走到B呢？换句话说，A和B是否是连通的.

定义union-find算法的接口UF

public interface UF {
    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();    //连通分量的数量
}

1.第一版 : quick-find

/**
 * 思路: 使用数组表示所有触点,连通的触点设置相同值即可
 * 特点: 使用该算法解决动态连通性问题并且最后只得到一个连通分量,
 *        则至少需要调用n-1次union(),每次都要遍历数组,即至少(n+3)(n-1) ~ N*N次数组访问,
 *        算法时间复杂度为平方级别的
 */
public class QuickFind implements UF{
    private int[] id;   //分量id,以触点作为索引
    private int count;  //分量数量
    //初始化N(0 ~ n-1)个触点
    public QuickFind(int N) {
        count = N;
        id = new int[N];
        for(int i=0;i<N;++i)
            id[i] = i;
    }

    //在p与q之间添加一条连接
    @Override
    public void union(int p,int q){
        int idp = find(p);
        int idq = find(q);
        if(idp == idq)
            return;
        for(int i=0;i<id.length;++i){
            if(id[i] == idq)
                id[i] = idp;
        }
        count--;
    }
    //p所在分量的标识符
    @Override
    public int find(int p){
        return id[p];
    }

    //判断是否连接
    @Override
    public boolean connected(int p, int q){
        return find(p) == find(q);
    }

    //连通分量数量
    @Override
    public int count(){
        return count;
    }

    //打印结果
    public void print(){
        for(int i:id){
            System.out.print(i+" ");
        }
    }
}

2.改进1: quick-union

/**
 *  思路: 每个触点值记录下一个触点数组索引
 *  特点: 执行union()方法时不需要遍历整个数组, 只需要遍历同一分量的触点(与树高成正比)
 *        假设输入整数对为0-1 0-2 0-3 ... 0-(n-1),此时为最坏情况,时间复杂度为平方级别
 */
public class QuickUnion implements UF{
    private int[] id;   //父连接数组,以触点作为索引
    private int count;  //分量数量

    public QuickUnion(int n){
        count = n;
        id = new int[n];
        for(int i=0;i<n;++i)
            id[i] = i;
    }
    @Override
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ)
            return;
        id[rootP] = rootQ;
        count--;

    }

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

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

    @Override
    public int count() {
        return count;
    }

    //打印结果
    public void print(){
        for(int i:id)
            System.out.print(i + " ");
    }
}

3.改进2: 加权quick-union

/**
 * 概述: 通过quick-union中union()方法可以发现,每次执行union()时,需要找到树根节点,
 *       因此考虑降低同一分量生成的树高,但同时节点多的树(大树)更容易被union()方法使用到,
 *       所以,在2个树合并时,优先选择降低大树的高度,即直接将小树(节点少)根节点指向大树(节点多)根节点.
 * 思路: 每个触点的值记录下一个触点数组索引,生成树形结构合并时,将小树根节点指向大树根节点
 *
 */
public class WeightedQuickUnion implements UF {
    int[] id;  //父连接数组,以触点作为索引
    int count; //分量数量
    int[] sz;  //记录触点所在树的节点个数

    public WeightedQuickUnion(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;
        }
    }

    @Override
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ)
            return;
        //连通规则: 将小树(节点少)根节点指向大树(节点多)根节点
        if(sz[rootP] > sz[rootQ]) {
            id[rootQ] = rootP;
            sz[rootP] += sz[rootQ];
        }
        else{
            id[rootP] = rootQ;
            sz[rootQ] += sz[rootP];
        }
        count--;
    }

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

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

    @Override
    public int count() {
        return count;
    }

    //打印结果
    public void print(){
        for(int i:id){
            System.out.print(i+" ");
        }
    }
}

4.改进3: 路径压缩加权quick-union

package cn.com.lock;

/**
 * 思路: 在加权quick-union算法基础上,在find()方法中直接将节点连接到根节点(压缩搜索路径)
 */
public class PathCompressionWQU implements UF{
    int[] id;  //父连接数组,以触点作为索引
    int count; //分量数量
    int[] sz;  //记录触点所在树的节点个数

    public PathCompressionWQU(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;
        }
    }

    @Override
    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP == rootQ)
            return;
        //连通规则: 将小树(节点少)根节点指向大树(节点多)根节点
        if(sz[rootP] > sz[rootQ]) {
            id[rootQ] = rootP;
            sz[rootP] += sz[rootQ];
        }
        else{
            id[rootP] = rootQ;
            sz[rootQ] += sz[rootP];
        }
        count--;
    }

    @Override
    public int find(int p) {
        int start = p;  //记录开始节点的值
        while(p != id[p]) //1. 循环结束后根节点为p
            p = id[p];

        //将节点连接到根节点,压缩搜索路径
        //2. 再次循环,将节点都指向根节点p (除了开始节点,无法获取到索引)
        while(start != p){  //处理没有指向根节点的节点,将其指向根节点 (不含开始节点)
            int next = id[start];
            id[start] = p;
            start = next;
        }

        //返回根节点
        return p;
    }

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

    @Override
    public int count() {
        return count;
    }

    //打印结果
    public void print(){
        for(int i:id){
            System.out.print(i+" ");
        }
    }
}