关于数据结构和算法:cs61b-week8-Disjoint-Sets

1.Introduce

并查集是一种数据结构，能够很不便地判断两个元素是否属于同一汇合，对于并查集的演示 demo，能够参考 slides 或其余路径，本次课 Josh 老师循序渐进地从并查集的数据结构抉择开始一步步优化，最终使并查集失去绝对较好的性能体现。简略来讲，并查集须要领有两个性能:

• isConnected()：判断两个元素之间是否相连接(属于同一汇合)
• Connect(): 连贯两个元素，在连贯之前应该判断元素是否已相连

因而咱们创立一个 DisjointSets 接口，并在继承它的子类里实现上述两种办法：

public interface DisjointSets {
    /** Connects two items P and Q. */
    void connect(int p, int q);
 
    /** Checks to see if two items are connected. */
    boolean isConnected(int p, int q);
}

2.ListOfSetsDS

首先的问题是: 如何去示意各个不相交汇合, 一说到汇合，很容易想到应用 Java 内置的 Set，那么就会有 \(Set_{0},Set_{1},Set_{2}……\)
因而能够应用 List<Set<Integer>> 的模式示意，这里假如元素类型是 Integer，其实视频里说，这是 Berkeley 学生的想法，我也没想到，（= =）这种数据结构看起来比较复杂，Josh 说实现起来也很简单，然而我感觉不算简单，说说我的想法。
比方想要把 \(Set_{0}中的元素 1 和 Set_{1}中的元素 2\)相连，思考:
IsConnected()：\(调用 Set_{0}.contains()即可 \)，应用 HastSet 的话，工夫复杂度应该低于 \(\Theta(N)\)
Connect()：\(调用 Set_{0}.add()即可，假如 Set_{1}的大小为 M，则工夫复杂度为 \Theta(M)\)
然而只是最开始还算比拟快，如果把一个 List 中的 Set 全副两两合并，越到前面执行单次合并的工夫复杂度就越高。

Performance Summary

3.QuickFindDS(疾速查找)

经验了下面的想法之后，咱们的想法是: 并查集的底层数据结构应该是 数组 。且为了实现疾速查找的性能，须要一些改变
具体实现为:
首先对于各个不相交的汇合，给每一个汇合一个 id，数组下标代表单个元素的值，数组外面存值为 id，对于属于同一个汇合内的元素，则存储雷同的 id 值, 图例:

如图, 假如 {0,1,4,2} 属于汇合 4，则在数组下标为 0 , 1 , 2 , 4 处的值都贮存为 4，那么当初考虑一下并查集的两个操作:
IsConnected()：i 和 j 是否属于同一汇合，只需比拟 a[i]与 a[j]的值，工夫复杂度为 O(1)
Connect()：遍历数组，如果连贯(2,3) 以上图为例，只需将 a[0],a[1],a[2],a[4]改为 5，也就是将汇合 1 中全副的元素的汇合 id 都改为汇合 2 的汇合 id，工夫复杂度为 O(N)

代码实现

public class QuickFindDS implements DisjointSets {private int[] id;

    public QuickFindDS(int N) {id = new int[N];
        for (int i = 0; i < N; i++)
            id[i] = i;
        }
    }  

    public boolean isConnected(int p, int q) {return id[p] == id[q];
    }
 
    public void connect(int p, int q) {int pid = id[p];
            int qid = id[q];
           for (int i = 0; i < id.length; i++) {if (id[i] == pid) {id[i] = qid;
            }
            }...

Performance Summary

4.Quick Union(疾速合并)

下面咱们实现了并查集的疾速查找，判断两个元素是否属于同一汇合的效率达到 O(1), 然而对于合并操作其效率为 O(N)，因为须要遍历整个数组，把属于同一个汇合中的元素对应的原来的汇合 id 更改为新的。
那么如何放慢合并操作的效率呢? 在原来的根底上，数组外面的存储的值不再是汇合的 id，而是各个元素的父节点的值。例如:

4 的父节点是 0，2 的父节点是 1，1 的父节点是 0，5 的父节点是 3，0 和 6 的父节点是其自身，那么在数组中，下标代表元素本身的值，而数组外面的存值存储父节点的值，父节点是本身的存储为 -1，造成如下的 树形构造(孩子双亲表示法):

那么当初如果想要连贯(5,2), 只须要寻找 5 的根节点 –3 和 2 的根节点 –0, 而后将 3 作为 0 的儿子连贯即可，将 a[3]=0

如此一来，合并操作效率变为了 O(1)，只需一步操作，更改汇合的根节点对应值即可。
然而事实上，查找的效率不再是 O(1)，假如咱们判断两个元素 a,b 是否相连:
IsConnected(): 查找 a 的根，查找 b 的根，判断是否相等，工夫复杂度为 O(H)，其中 H 为树的高度，最坏状况下，如果树的形态是这样的:

那么查找的工夫复杂度是 O(N)
因为每次进行合并前均须要判断是否曾经相连操作，因而，只管合并只须要一步，然而总的工夫复杂度依然是 O(N)

代码实现

public class QuickUnionDS implements DisjointSets {private int[] parent;
    public QuickUnionDS(int N) {parent = new int[N];
            for (int i = 0; i < N; i++) 
              {parent[i] = -1; }
           }
 
      private int find(int p) {
            int r = p;
        while (parent[r] >= 0) 
              {r = parent[r]; }
           return r;
    }

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

    public void connect(int p, int q) {int i = find(p);
        int j = find(q);
        parent[i] = j;
}

Performance Summary

5. 改良 1 Weighted Quick Union(加权疾速合并)

下面咱们看到，要想查找的效率为 O(1)，则合并的步骤须要 O(N)，要想一步即实现合并，那么查找须要 O(N)，仿佛二者是不可兼得的，而且对于孩子双亲表示法，树越高那么查找的性能就越差，因为查找的过程是相当于爬树，如何防止合并过程中树变得越来越高也是一个重要的优化过程。
对于两个汇合的合并，咱们很容易想到，通过比拟两棵树的高度，将矮树的根 作为 高树的根的子树，这样能够防止树高度的减少，均匀查找效率为 O(logN)
然而 换一种思路 :
一棵树的所有结点数量定义为该树的权 (Weight)，咱们总是将小树的根连贯到大树的根上。

因而当初咱们要想方法追踪权值，可选的办法有:

• 1. 根节点在数组中的值不再存储 -1，而是存储 负权值

• 2. 再开一个 size 数组，专门存储对应的结点的权值

两种办法都能够，那么让咱们来考虑一下按权疾速合并的工夫复杂度:
假如当初只有一个元素 0：

树的高度为 0，元素个数 1
当初合并 0 和 1:

树的高度为 1，元素个数 2
要想将树的高度从 1 变为 2，只减少 1 个元素是不行的，假如合并 1 和 2，依照按权合并的规定，将小树 2 的根作为大树 0 的根的孩子:

树的高度仍然为 1，因而 3 个元素不可能使树的高度为 2，要想让树的高度 +1，须要四个元素:

同理可类推，要想树的高度为 3，须要 8 个元素:


要想树的高度为 4，须要 16 个元素:

察看可知最坏状况下树的高度为 \(log_{2}N\)，因而工夫复杂度为 \(\Theta(N)\)
那么其实按权合并和按高度合并的工夫复杂度都是 \(\Theta(N)\)，为何抉择按权合并呢?
是因为在雷同的 \(\Theta(N)\)下，按权合并的代码实现更简略

Performance Summary

6. 改良 2 Path Compression(门路压缩)

考虑一下，假如咱们要判断 15 和 10 是否连贯，须要查找:
15–>11–>5–>1
再查找 10–>3–>0

须要 logN 的工夫进行查找，再合并，假如在查找的过程中，将沿途通过的结点的父结点全副都改成根节点 0，让他们间接隶属于根节点:

那么下次再判断 15 和 10 是否相连时，只须要 O(1) 的操作，这就是门路压缩。
代码:

int find(int x)
{if(fa[x] < 0)
        return x;
    else{fa[x] = find(fa[x]); 
        return fa[x];        
    }
}

这里说门路压缩的效率是严格来说是 \(O(\alpha(N), 其中,\alpha(N)是反阿克曼函数，非常靠近常数 \)
proved by Tarjan here at UC Berkeley in 1975
其增长与 N 的关系为:

Performance Summary

假如对 N 个元素的并查集进行 M 次操作，工夫复杂度表:

文章举荐
门路压缩
并查集