06--图解数据结构之并查集

连接问题--网络中节点间的连接状态
节点、边--isConnrcted(p,q)
集合的并集---union(p,q)

并查询连接.png

并查集接口

/**
 * 作者：张风捷特烈
 * 时间：2018/9/25 0025:11:09
 * 邮箱：[email protected]
 * 说明：并查集接口
 */
public interface IUF {
    /**
     * 查看p,q元素是否属于同一集合
     *
     * @param p p元素
     * @param q q元素
     * @return 是否属于同一集合
     */
    boolean isConnected(int p,int q);

    /**
     * 联合p，q所在集合
     * @param p p元素
     * @param q q元素
     */
    void unionEl(int p, int q);

    /**
     * 元素个数
     * @return 元素个数
     */
    int size();
}

第一版：快速查询的并查集

/**
 * 作者：张风捷特烈
 * 时间：2018/9/25 0025:11:15
 * 邮箱：[email protected]
 * 说明：快速查询并查集
 */
public class QuickFindUF implements IUF {

    private int[] id;

    public QuickFindUF(int size) {
        id = new int[size];
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

    @Override
    public boolean isConnected(int p, int q) {

        return find(p) == find(q);
    }

    @Override
    public void unionEl(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;
            }
        }
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= id.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        return id[p];
    }

    @Override
    public int size() {
        return id.length;
    }
}

isConnected方法复杂度O(1)
unionEl方法复杂度O(n)

第二版：快速合并并查集

/**
 * 作者：张风捷特烈
 * 时间：2018/9/25 0025:11:15
 * 邮箱：[email protected]
 * 说明：快速合并并查集
 */
public class QuickUnionUF implements IUF {
    private int[] parent;

    public QuickUnionUF(int size) {
        parent = new int[size];
        //每个节点都是一颗树
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }

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

    @Override
    public void unionEl(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }


        parent[pRoot] = qRoot;
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int size() {
        return parent.length;
    }
}

基于树实现，isConnected和unionEl的复杂度O(logn),但有可能退化到O(n)

第三版：改良型----基于集合节点数连接

/**
 * 作者：张风捷特烈
 * 时间：2018/9/25 0025:11:15
 * 邮箱：[email protected]
 * 说明：快速合并并查集优化
 */
public class QuickUnion2UF implements IUF {
    private int[] parent;
    /**
     * 以treeSize[i]为根的集合元素个数
     */
    private int[] treeSize;

    public QuickUnion2UF(int size) {
        parent = new int[size];
        treeSize = new int[size];
        //每个节点都是一颗树
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            treeSize[i] = 1;
        }
    }

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

    @Override
    public void unionEl(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        if (treeSize[pRoot] < treeSize[qRoot]) {
            parent[pRoot] = qRoot;
            treeSize[qRoot] += treeSize[pRoot];
        } else {
            parent[qRoot] = pRoot;
            treeSize[pRoot] += treeSize[qRoot];
        }
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int size() {
        return parent.length;
    }
}

第三版：改良型----基于集合树深数连接

/**
 * 作者：张风捷特烈
 * 时间：2018/9/25 0025:11:15
 * 邮箱：[email protected]
 * 说明：快速合并并查集优化
 */
public class QuickUnion3UF implements IUF {
    private int[] parent;
    /**
     * 以rank[i]为根的集合元素个数
     */
    private int[] rank;

    public QuickUnion3UF(int size) {
        parent = new int[size];
        rank = new int[size];
        //每个节点都是一颗树
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

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

    @Override
    public void unionEl(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);
        if (pRoot == qRoot) {
            return;
        }
        //按照深度来连接
        if (rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = qRoot;
        } else if (rank[qRoot] < rank[pRoot]) {
            parent[qRoot] = pRoot;
        } else {
            parent[qRoot] = pRoot;
            rank[pRoot] += 1;
        }
    }

    /**
     * 查找元素p所对应的集合编号
     *
     * @param p 元素
     * @return p所对应的集合编号
     */
    private int find(int p) {
        if (p < 0 || p >= parent.length) {
            throw new IllegalArgumentException("p is out of bound.");
        }
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public int size() {
        return parent.length;
    }
}

时间分析：

unionEl方法册数测试：size=10000

unionEl方法册数测试：size=100000

unionEl方法册数测试：size=1000000

unionEl方法册数测试：size=10000000

后记、

1.声明：

[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明