一、奇怪的树结构

由子节点指向父节点,连接问题 Connectivity Problem

连接问题.png

网络中节点间的连接状态

• 网络是个抽象的概念：例如用户之间形成之间的网络
• 数学中集合类的实现

连接问题和路径问题相比，连接问题比路径问题要回答的问题少？

并查集Union Find.png

元素个数是固定的，没有添加和删除操作，只针对已存在的进行分析

并查集实现的接口

UF

public interface UF {

    int getSize();
    boolean isConnected(int p, int q);
    void unionElements(int p, int q);
}

二、Quick Find查找很快(第一版)

描述：略，请直接观察代码

查找的复杂度为O(1)

// 我们的第一版Union-Find
public class UnionFind1 implements UF{

    private int[] id;

    public UnionFind1(int size) {
        id = new int[size];
        for (int i = 0; i < size; 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("error");

        return id[p];
    }

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

    // 合并元素p和元素q所属的集合
    @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;
        }
    }
}

Quick Union连接很快(第二版)

描述：将所有元素抽象为一个静态数组，数组的索引对应为自己的id，初始化所有id的值都是保存的自己的索引，可以理解为初始化时所有的元素都指向的为自己，当将两个id进行 连接操作(unionElements) 的时候,分别查询自己保存的id,然后再查询以此id为索引保存的值是否等于查询的索引，如果不相等则继续找，直到查询到索引与保存的索引相等；分别找到索引后 【这里有优化空间,详见第三版】 随机将一个索引的值保存为另一个索引。对应的 查询操作(isConnected) 就变得十分简单了，找到指向的根节点(对应索引的位置保存的为当前索引)，并判断是否相等。

储存方式还是数组，但是逻辑层面是森林(很多树),子节点指向父节点，一层一层，直到一个节点指向自己

QuickUnion1.png

QuickUnon2.png

public class UnionFind2 implements UF{

    private int[] parent;

    public UnionFind2(int size) {
        this.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("error");

        while (p != parent[p])
            p = parent[p];

        return p;
    }

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

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

        if(pRoot != qRoot)
            parent[pRoot] = qRoot;
    }
}

• 第一版与第二版性能的比较！(并查集的长度一定)
  1. 当操作并查集的次数很少的时候，第一版的isConnected的复杂度为O(1),unionElements的复杂度为O(n),主要的性能消耗在了unionElements，耗时长；第二版的两个操作的复杂度都是O(h) ,h为该相关树的高度，树的深度很浅，总体性能优于第一版
  2. 当操作并查集的次数很多的时候，优于JVM对于数组遍历操作有很好的优化，性能不会差好多，但是对于第二版，此时的数的深度可能很深了，而且每次根据索引寻找具体地址进行取值会比第一版的遍历操作要差一些，当操作量大了之后就充分体现了，此时第一版的性能总体优于第二版

基于size的优化 (第三版)

为每个索引保存一个记录当前节点下对应的所有子节点数，在unionElements时，将子节点少的根节点指向子节点多的节点。从而减少树的深度，但是，子节点少就不一定代表次数最深深度比子节点多的最深深度要浅，【更进一步优化，请看下面的rank优化】

public class UnionFind3 implements UF {

    private int[] parent;
    private int[] count; // 储存parent每个节点下的所有子节点个数

    public UnionFind3(int size) {
        this.parent = new int[size];
        this.count = new int[size];

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

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


    private int find(int p) {

        while (p != parent[p])
            p = parent[p];

        return p;
    }

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

    @Override
    public void unionElements(int p, int q) {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if(count[p] < count[q]) {
            parent[p] = q;
            count[q] += count[p];
        } else {
            parent[q] = p;
            count[p] += count[q];
        }

    }
}

基于rank的优化(终极版a0.5)

基于rank的优化，rank[i]表示根节点为i的数的高度。

在unionElements时，将最深度小的数根节点指向最深度比较大的根节点，仅当两颗数最深度相等时，随机将一棵树指向另一棵树，并且维护一下这颗数的最深度(深度自增1，只有此步骤需要维护树的最大深度)

public class UnionFind4 implements UF {

    private int[] parent;
    private int[] rank; // 储存parent每个节点下的所有子节点个数

    public UnionFind4(int size) {
        this.parent = new int[size];
        this.rank = new int[size];

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

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

    private int find(int p) {

        while (p != parent[p])
            p = parent[p];

        return p;
    }

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

    @Override
    public void unionElements(int p, int q) {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if(rank[p] < rank[q])
            parent[p] = q;
        else if (rank[q] < rank[p])
            parent[q] = p;
        else {
            parent[p] = q;
            rank[q] += 1;
        }

    }
}

简单的路径压缩Path Compression(终极版a--终极奥义版)

思路：在终极版a0.5上进行优化，在find操作的时候进行路径压缩,减少深度parent\[p\] = parent\[parent\[p\]\]
如下图:

路径压缩1.png

路径压缩2.png

路径压缩3.png

路径压缩版实在终极版0.5的基础上的find方法上进行了优化，同时，这也导致rank记录的与树的最深深度不统一，但是丝毫不影响基于rank的比较！这就是为什么叫做rank而不叫depth或者height的原因

public class UnionFind5 implements UF {

    private int[] parent;
    private int[] rank; // 储存parent每个节点下的所有子节点个数

    public UnionFind5(int size) {
        this.parent = new int[size];
        this.rank = new int[size];

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

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

    private int find(int p) {
        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("Index is out of bounds!");

        while (p != parent[p]) {
            parent[p] = parent[parent[p]];
            p = parent[p];
        }

        return p;
    }

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

    @Override
    public void unionElements(int p, int q) {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if(rank[p] < rank[q])
            parent[p] = q;
        else if (rank[q] < rank[p])
            parent[q] = p;
        else {
            parent[p] = q;
            rank[q] += 1;
        }
    }
}

彻底的路径压缩(终极版b，性能略低于终极奥义版)

彻底的路径压缩：递归实现(只有递归到最深处，才能再一步一步重新定向),还是在find中进行操作，虽然保证了树的深度永远为1，但是，递归的开销是很大的，性能上不一定比终极版a要好，这就验证了有的必有失！(终极版a虽然不能一次性将深度变为1,但是在诸多的find操作下，已经非常非常靠近1了)

彻底的路径压缩.png

public class UnionFind6 implements UF {

    private int[] parent;
    private int[] rank; // 储存parent每个节点下的所有子节点个数

    public UnionFind6(int size) {
        this.parent = new int[size];
        this.rank = new int[size];

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

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

    private int find(int p) {

        if(p < 0 || p >= parent.length)
            throw new IllegalArgumentException("Index out of bounds.");

        // 如果写成了parent[p] = find(p) 则会形成死循环
        while (p != parent[p]) {
            parent[p] = find(parent[p]);
        }

        return parent[p];
    }

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

    @Override
    public void unionElements(int p, int q) {

        int pRoot = find(p);
        int qRoot = find(q);

        if(pRoot == qRoot)
            return;

        if(rank[p] < rank[q])
            parent[p] = q;
        else if (rank[q] < rank[p])
            parent[q] = p;
        else {
            parent[p] = q;
            rank[q] += 1;
        }
    }
}

更多喝并查集相关的话题

查询和连接操作的时间复杂度都是O(h)，但是h与n的关系是非常非常
复杂的数学关系，不需要去深究(我不搞数学)。

严格意义上，加入路径压缩的并查集的
时间复杂度为O(log*n)----> iterated logarithm

时间复杂度.png

上图的*是一种递归表示，就和计算机递归过程是一样的

O(log*n)是一种比O(log*n)更牛逼的，近乎等于O(1)级别