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>的形式表示，这里假设元素类型是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(快速查找)
【cs61b week8 -- Disjoint Sets】经历了上面的想法之后，我们的想法是:并查集的底层数据结构应该是数组。且为了实现快速查找的功能，需要一些改动
具体实现为:
首先对于各个不相交的集合，给每一个集合一个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