CS 61B 不相交集

笔记的来源：CS 61B-2024 春季的课程课程主要内容：数据结构与算法分析课程运用语言：Java

你可以在我的笔记网站里获得更多有用的资源。

这个课有6 个 Homework，10 个 Lab，9 个 Project。其中第一个 project 是一个完整的 2024 游戏的实现，很有意思。此文章对应的是课程 14 节的内容。主要讲述了一个不相交集的问题

不相交集问题

我们可以用下面的代码描述上图元素的互相关系

ds = DisjointSets(7)
ds.connect(0, 1)
ds.connect(1, 2)
ds.connect(0, 4)
ds.connect(3, 5)
ds.isConnected(2, 4): true
ds.isConnected(3, 0): false

而不相交集的问题就是实现ds的方法,我们要实现的是：

public class DisjointSets {
    void connect(int a, int b) {}
    boolean isConnected(int a, int b) {}
}

实现方法

集合列表

一开始我们有[{1},{2},{3},{4},{5},{6}] 对于连接操作，我们可以将a和b所在的集合合并，即[{1,2,3,4,5,6}]

void connect(int a, int b) {
    int setA = find(a);
    int setB = find(b);
    if (setA!= setB) {
        sets[setA].addAll(sets[setB]);
        sets.remove(setB);
    }
}

最后我们得到的算法性能为:

方法

初始化

连接

查询

集合列表

对于这个结果我们并不满意

快速查找

代码实现则是这样的：

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;
        }
    }
}

这个算法的性能如下：

方法

初始化

连接

查询

集合列表

快速查找

快速合并

我们已经通过给元素加标识的方法简化了查询操作的算法，接下来我们要利用树的方法来简化连接操作的算法。

如上图的这个结构，我们可以大概了解这个结构的实现。每当我们将两个元素连接的时候，我们将两个元素的根节点互相连接，就可以实现两个集合的合并。上述情况我们可以得到下表：

element

parent

-1

其中，作为根节点的元素的父节点为-1。接下来我们用代码实现：

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;
    }

...
}