数据结构与算法-并查集多种实现以及优化步骤

并查集所解决的问题

1. 网结构连接
2. 网结构各个结点是否连接

实现

常规实现

接口设计

public interface UF {
    public int getSize();

    public boolean isConnected(int id1,int id2);

    public void unionElements(int id1,int id2);
}

实现思路

用一段连续的地址空间，索引所谓键，值则是代表他们所在的集合对应的值。若要连接两个结点，就需要将一个堆元素移动到另一个堆中。
如下图所示：

实现代码

可以看出这种实现方式合理的利用了数组的特点，所以判断两个结点是否相连只需O(1)的时间，而连接则需要O(n)

package com.study.UnionFindDemo;

public class UnionFind1QuickFind implements UF {

    private int Ids[];

    /**
     * 初始化并查集时，每个元素对应的value为自己的索引， 各自独立。 
     *
     * @param size
     */
    public UnionFind1QuickFind(int size) {
        Ids = new int[size];

        for (int i = 0; i < size; i++) {
            Ids[i] = i;
        }
    }

    /**
     * 返回并查集的长度
     * @return 并查集的长度
     */
    @Override
    public int getSize() {
        return Ids.length;
    }

    /**
     * 判断两个节点，是否相连因为实现上是用数组所以查询速度很快，复杂度为O(1)
     * @param id1
     * @param id2
     * @return
     */
    @Override
    public boolean isConnected(int id1, int id2) {
        if (isOutofIndex(id1) || isOutofIndex(id2))
            throw new IllegalArgumentException("索引越界");
        int value1 = findValue(id1);
        int value2 = findValue(id2);

        return value1==value2;
    }


    private boolean isOutofIndex(int index) {
        return index < 0 || index >= Ids.length;
    }

    /**
     * 查看当前节点对应value值
     * @param index
     * @return 节点的value
     */
    private int findValue(int index) {

        if (isOutofIndex(index) )
            throw new IllegalArgumentException("索引越界");
        return Ids[index];
    }

    /**
     * 将两个没有联系的节点连接起来，节点有可能有其他相连节点，所以相当于将两棵树连接起来，
     * 因为需要遍历 所以复杂度为O(n)
     * @param id1
     * @param id2
     */
    @Override
    public void unionElements(int id1, int id2) {
        int value1=findValue(id1);
        int value2=findValue(id2);

        if (value1==value2)
            return;

        //将一个堆移动到另一个堆中
        for (int i = 0; i <Ids.length ; i++) {
            if (Ids[i]==value2)
                Ids[i]=value1;
        }
    }
}

逻辑上的树结构优化连接

实现思路

连接两个结点时，让作为子节点的指向父节点，这样仅仅牺牲了查找的时间，却大大优化了连接的复杂度。具体实现如下图所示，想连接3 5结点时，只需将彼此的父节点连接起来即可：

实现代码

package com.study.UnionFindDemo;

public class UnionFindByParent implements UF {

    private int parent[];

    /**
     * 初始化并查集时，每个元素对应的value为自己的索引 各自独立 逻辑上可以看成一个森林
     *
     * @param size
     */
    public UnionFindByParent(int size) {
        parent = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }
    }

    /**
     * 返回并查集的长度
     *
     * @return 并查集的长度
     */
    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 判断两个节点 是否相连 构成一个网,即是否可达，因为实现上是用数组所以复杂度为O(h)
     *
     * @param id1
     * @param id2
     * @return
     */
    @Override
    public boolean isConnected(int id1, int id2) {
        if (isOutofIndex(id1) || isOutofIndex(id2))
            throw new IllegalArgumentException("索引越界");
        int value1 = findIndex(id1);
        int value2 = findIndex(id2);

        return value1 == value2;
    }


    private boolean isOutofIndex(int index) {
        return index < 0 || index >= parent.length;
    }

    /**
     * 查看当前节点对应value值
     *因为查询的时高度 所以复杂度为 O(h)  h为树的高度
     * @param p 初始化时每个结点的值==索引
     * @return 根节点的索引
     */
    private int findIndex(int p) {

        if (isOutofIndex(p))
            throw new IllegalArgumentException("索引越界");
        //不断循环找到根结点
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;

    }

    /**
     * 找到两个结点对应的父节点再将另一个父节点的值改为子节点的值即可
     * 复杂度为O(h)
     *
     * @param id1
     * @param id2
     */
    @Override
    public void unionElements(int id1, int id2) {
        int index1 = findIndex(id1);
        int index2 = findIndex(id2);

        if (index1 == index1)
            return;

        parent[index2]=index1;
    }
}

基于size优化parent并查集

实现思路与介绍

可以看出上述步骤虽然优化了连接的复杂度，但是在极端情况下这种连接方式可能会退化成链表，对此我们的解决方案时用size小的树连接大的那棵树，从而做到减小深度。具体实现如下图所示:

实现代码

package com.study.UnionFindDemo;

public class UnionFindByChildSize implements UF {

    private int parent[];
    private int childSize[];

    /**
     * 初始化并查集 每个元素对应的value为自己的索引 各自独立 逻辑上可以看成一个森林
     * 每个结点 初始化 子节点个数为1 即就它自己一个
     * @param size
     */
    public UnionFindByChildSize(int size) {
        parent = new int[size];
        childSize = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
            childSize[i] = 1;
        }
    }

    /**
     * 返回并查集的长度
     *
     * @return 并查集的长度
     */
    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 判断两个节点 是否相连 构成一个网,即是否可达，因为实现上是用数组所以复杂度为O(h)
     *
     * @param id1
     * @param id2
     * @return
     */
    @Override
    public boolean isConnected(int id1, int id2) {
        if (isOutofIndex(id1) || isOutofIndex(id2))
            throw new IllegalArgumentException("索引越界");
        int value1 = findIndex(id1);
        int value2 = findIndex(id2);

        return value1 == value2;
    }


    private boolean isOutofIndex(int index) {
        return index < 0 || index >= parent.length;
    }

    /**
     * 查看当前节点对应value值
     * 因为查询的时高度 所以复杂度为 O(h)
     *
     * @param p 初始化时每个结点的值==索引
     * @return 根节点的索引
     */
    private int findIndex(int p) {

        if (isOutofIndex(p))
            throw new IllegalArgumentException("索引越界");
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;

    }

    /**
     * 找到两个结点对应的父节点再将另一个父节点的值改为子节点的值即可
     * 复杂度为O(h)
     *
     * @param id1
     * @param id2
     */
    @Override
    public void unionElements(int id1, int id2) {
        int index1 = findIndex(id1);
        int index2 = findIndex(id2);

        if (index1 == index1)
            return;

        //结点数小的连接结点数大的 避免增加树的深度
        if (childSize[index1]<childSize[index2]){
            parent[index1]=parent[index2];
            childSize[index2]+=childSize[index1];
        }else{
            parent[index2]=parent[index1];
            childSize[index1]+=childSize[index2];
        }
    }
}

基于rank的优化解决size的不足

简介以及实现思路

当出现下图情况时，基于size的优化照样会出现增加深度的情况，所以我们需要基于树的深度rank进行优化。
具体实现思路很简单，默认每个结点深度为1，当两个深度一样的树结合时，可让任意一颗树连接另一颗树，被连接的树的深度基于原来+1即可。
其他情况深度不变，深度小的连接大的即可

实现代码

package com.study.UnionFindDemo;


public class UnionFindByRank implements UF {

    private int parent[];
    private int rank[];

    /**
     * 初始化并查集 每个元素对应的value为自己的索引 各自独立 逻辑上可以看成一个森林
     *
     * @param size
     */
    public UnionFindByRank(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i;
            rank[i]=1;
        }
    }

    /**
     * 返回并查集的长度
     *
     * @return 并查集的长度
     */
    @Override
    public int getSize() {
        return parent.length;
    }

    /**
     * 判断两个节点 是否相连 构成一个网,即是否可达，因为实现上是用数组所以复杂度为O(h)
     *
     * @param id1
     * @param id2
     * @return
     */
    @Override
    public boolean isConnected(int id1, int id2) {
        if (isOutofIndex(id1) || isOutofIndex(id2))
            throw new IllegalArgumentException("索引越界");
        int value1 = findIndex(id1);
        int value2 = findIndex(id2);

        return value1 == value2;
    }


    private boolean isOutofIndex(int index) {
        return index < 0 || index >= parent.length;
    }

    /**
     * 查看当前节点对应value值
     * 因为查询的时高度 所以复杂度为 O(h)
     *
     * @param p 初始化时每个结点的值==索引
     * @return 根节点的索引
     */
    private int findIndex(int p) {

        if (isOutofIndex(p))
            throw new IllegalArgumentException("索引越界");
        while (p != parent[p]) {
            p = parent[p];
        }
        return p;

    }

    /**
     * 找到两个结点对应的父节点再将另一个父节点的值改为子节点的值即可
     * 复杂度为O(h)
     *
     * @param id1
     * @param id2
     */
    @Override
    public void unionElements(int id1, int id2) {
        int index1 = findIndex(id1);
        int index2 = findIndex(id2);

        if (index1 == index1)
            return;
        if (rank[index1]<rank[index2]){
            parent[index1]=parent[index2];
        }else if (rank[index1]>rank[index2]){
            parent[index2]=parent[index1];
        }else{
            parent[index1]=parent[index2];
            rank[index1]+=1;
        }
    }
}

改进

这样连接的树可能还是会增加深度，我们可以在find时，让当前结点的父节点指向父节点的父节点，如下图所示，从而在查找时优化这个树的深度。

实现代码

  /**
     * 查看当前节点对应value值
     * 因为查询的时高度 所以复杂度为 O(h)
     * 增加了优化高度的操作
     * @param p 初始化时每个结点的值==索引
     * @return 根节点的索引
     */
    private int findIndex(int p) {

        if (isOutofIndex(p))
            throw new IllegalArgumentException("索引越界");
        while (p != parent[p]) {
            parent[p]=parent[parent[p]];
            p = parent[p];
        }
        return p;

    }

基于递归完成最优树

上述步骤我们可以用递归完成最优树代码如下

 /**
     * 查看当前节点父节点对应value值
     * 因为查询的时高度 所以复杂度为 O(h)
     * 增加了优化高度的操作 用递归完成最优树
     * @param p 初始化时每个结点的值==索引
     * @return 根节点的索引
     */
    private int findIndex(int p) {

        if (isOutofIndex(p))
            throw new IllegalArgumentException("索引越界");
        while (p != parent[p]) {
            //让结点的父亲结点指向根节点
            parent[p]=findIndex(p);
        }
        return parent[p];

    }

补充

O(h)复杂度计算复杂为O(log*n),近乎O(1)的级别，我们这里记住结论即可