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

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

并查询连接.png

并查集接口

/**
 * 作者：张风捷特烈
 * 时间：2018/9/25 0025:11:09
 * 邮箱：1981462002@qq.com
 * 说明：并查集接口
 */
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
 * 邮箱：1981462002@qq.com
 * 说明：快速查询并查集
 */
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
 * 邮箱：1981462002@qq.com
 * 说明：快速合并并查集
 */
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
 * 邮箱：1981462002@qq.com
 * 说明：快速合并并查集优化
 */
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
 * 邮箱：1981462002@qq.com
 * 说明：快速合并并查集优化
 */
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

方法\数量	复杂度	1000	10000	10W	100W	1000W
QuickFindUF	O(n)	0.0197秒	0.0880秒	0.1199秒	0.1688秒	0.5216秒
QuickUnionUF	O(logn)	0.0015秒	0.0132秒	0.7418秒	7.0839秒	----秒
quickUnion2UF	O(logn)	0.0017秒	0.0050秒	0.0220秒	0.0966秒	0.6657秒

---

unionEl方法册数测试：size=100000

方法\数量	复杂度	1000	10000	10W	100W	1000W
QuickFindUF	O(n)	0.0197秒	0.0880秒	0.1199秒	0.1688秒	10.0468秒
QuickUnionUF	O(logn)	0.0015秒	0.0132秒	0.7418秒	7.0839秒	----秒
quickUnion2UF	O(logn)	0.0017秒	0.0050秒	0.0220秒	0.0966秒	0.8478秒

---

unionEl方法册数测试：size=1000000

方法\数量	复杂度	1000	10000	10W	100W	1000W
QuickFindUF	O(n)	0.6346秒	5.3409秒	----秒	----秒	----秒
QuickUnionUF	O(logn)	0.0012秒	0.0052秒	0.0281秒	----秒	----秒
quickUnion2UF	O(logn)	0.0013秒	0.0062秒	0.0304秒	0.2186秒	1.8915秒

---

unionEl方法册数测试：size=10000000

方法\数量	复杂度	1000	10000	10W	100W	1000W
quickUnion2UF	O(logn)	0.0013秒	0.0063秒	0.0335秒	0.1903秒	2.5726秒
quickUnion3UF	O(logn)	0.0016秒	0.0060秒	0.0323秒	0.1932秒	2.5327秒

---

后记、

1.声明：

[1]本文由张风捷特烈原创,各图均由本人亲自所画，转载请注明
[2]欢迎广大编程爱好者共同交流
[3]个人能力有限，如有不正之处欢迎大家批评指证，必定虚心改正
[4]你的喜欢与支持将是我最大的动力

2.连接传送门：

更多数据结构知识欢迎访问:图解数据结构
项目源码均在我的https://github.com/toly1994328/DS：欢迎star
张风捷特烈个人网站，编程笔记请访问：http://www.toly1994.com

3.联系我

QQ:1981462002
邮箱：1981462002@qq.com
微信：zdl1994328

4.欢迎关注我的微信公众号，最新精彩文章，及时送达：

公众号.jpg