数据结构--并查集

并查集

由孩子指向父亲，快速判断节点连接状态。可用于解决连接问题，就集合的并集。

集合

//interface
public interface UnionFind {
    int getSize();
    boolean isConnected(int p, int q);
    void unionElements(int p, int q);
}

public class UnionFind1 implements UnionFind {

    private int[] id;

    public UnionFind1(int size) {
        id = new int[size];
        //每个元素都所属不同的集合
        for (int i = 0; i < id.length; i++) {
            id[i] = i;
        }
    }

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

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

    //查看元素p与q是否属于同一个集合 O(1)
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //合并元素p与元素q所属的集合  O(n)
    @Override
    public void unionElements(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;
        }
    }
}

//时间复杂度 O(log^*n) 近乎于O(1)

优化一

孩子指向父亲，依然用数组表示，但是形成的是树结构。

union

仍然可以使用数组表示

初始状态
union

public class UnionFind2 implements UnionFind {

    private int[] parent;

    public UnionFind2(int size) {
        parent = new int[size];

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

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

    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h为树的高度
    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;

    }

    //O(h)复杂度，h为树的高度
    //查看元素p与q是否属于同一个集合 O(1)
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //O(h)复杂度，h为树的高度
    //合并元素p与元素q所属的集合  O(n)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;

        parent[pRoot] = parent[qRoot];
    }
}

优化二

让节点个数少的根节点指向节点个数多的根节点。

优化二

public class UnionFind3 implements UnionFind {

    private int[] parent;
    private int[] sz;

    public UnionFind3(int size) {

        parent = new int[size];

        //sz[i]表示以i为根的集合中元素个数
        sz = new int[size];

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

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

    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h为树的高度
    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;

    }

    //O(h)复杂度，h为树的高度
    //查看元素p与q是否属于同一个集合 O(1)
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //O(h)复杂度，h为树的高度
    //合并元素p与元素q所属的集合  O(n)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;

        //根据俩个元素所在树的元素个数不同判断合并方向
        //将元素个数少的集合合并到元素个数多的集合上
        if(sz[pRoot] < sz[qRoot]) {
            parent[pRoot] = parent[qRoot];
            sz[qRoot] += sz[pRoot];
        }
        else { // sz[pRoot] >= sz[qRoot]
            parent[qRoot] = parent[pRoot];
            sz[pRoot] += sz[qRoot];
        }
    }
}

//时间复杂度 O(log^*n) 近乎于O(1)

优化三

基于rank的优化，rank[i]表示根节点为i的树的高度。
让深度比较少的树向深度比较高的树进行合并。

优化三

public class UnionFind4 implements UnionFind {

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

    public UnionFind4(int size) {

        parent = new int[size];

        //rank[i]表示以i为根的集合所表示的树的层数
        rank = new int[size];

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

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

    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h为树的高度
    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;

    }

    //O(h)复杂度，h为树的高度
    //查看元素p与q是否属于同一个集合 O(1)
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //O(h)复杂度，h为树的高度
    //合并元素p与元素q所属的集合  O(n)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;

        //根据俩个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if(rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = parent[qRoot];
        } else if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = parent[pRoot];
        }
        else { // =
            parent[qRoot] = parent[pRoot];
            rank[pRoot] += 1;
        }
    }
}

//时间复杂度 O(log^*n) 近乎于O(1)

优化四

路径压缩，将高树压缩成矮树

优化四
4.1
4.2
4.3

public class UnionFind5 implements UnionFind {

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

    public UnionFind5(int size) {

        parent = new int[size];

        //rank[i]表示以i为根的集合所表示的树的层数
        rank = new int[size];

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

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

    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h为树的高度
//    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;
//    }


    //优化 路径压缩 经典优化思路
    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h为树的高度
    private int find(int p) {

        if (p < 0 && p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");

        //没有改变rank 使用粗略的rank值已经能满足性能
        while (p != parent[p])
            parent[p] = parent[parent[p]];
            p = parent[p];
        return p;
    }

    //O(h)复杂度，h为树的高度
    //查看元素p与q是否属于同一个集合 O(1)
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //O(h)复杂度，h为树的高度
    //合并元素p与元素q所属的集合  O(n)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;

        //根据俩个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if(rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = parent[qRoot];
        } else if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = parent[pRoot];
        }
        else { // =
            parent[qRoot] = parent[pRoot];
            rank[pRoot] += 1;
        }
    }
}

//时间复杂度 O(log^*n) 近乎于O(1)

优化五

使用递归，将查询的节点，以及其之前的节点都直接指向跟节点

优化五

public class UnionFind6 implements UnionFind{

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

    public UnionFind6(int size) {

        parent = new int[size];

        //rank[i]表示以i为根的集合所表示的树的层数
        rank = new int[size];

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

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

    //优化 路径压缩 经典优化思路
    //查找过程，查找元素p所对应的集合编号
    //O(h)复杂度，h为树的高度
    private int find(int p) {

        if (p < 0 && p >= parent.length)
            throw new IllegalArgumentException("p is out of bound");

        if (p != parent[p])
            parent[p] = find(parent[p]);
        return parent[p];
    }

    //O(h)复杂度，h为树的高度
    //查看元素p与q是否属于同一个集合 O(1)
    @Override
    public boolean isConnected(int p, int q) {
        return find(p) == find(q);
    }

    //O(h)复杂度，h为树的高度
    //合并元素p与元素q所属的集合  O(n)
    @Override
    public void unionElements(int p, int q) {
        int pRoot = find(p);
        int qRoot = find(q);

        if (pRoot == qRoot)
            return;

        //根据俩个元素所在树的rank不同判断合并方向
        //将rank低的集合合并到rank高的集合上
        if(rank[pRoot] < rank[qRoot]) {
            parent[pRoot] = parent[qRoot];
        } else if (rank[pRoot] > rank[qRoot]) {
            parent[qRoot] = parent[pRoot];
        }
        else { // =
            parent[qRoot] = parent[pRoot];
            rank[pRoot] += 1;
        }
    }
}
//时间复杂度 O(log^*n) 近乎于O(1)