5 - Disjoint Sets

0 写在前面

话说回来，好像大一下学期我最满意的笔记就是并查集的笔记了，好像是从那时开始在b站上看一些视频自己学数据结构了？

没想到还有自己给自己打广告的时候，不过这个网站我已经不再更新了，数据结构笔记 - 并查集

1 Introduction

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

并查集有两个操作，一是判断两个元素是否相连，另一个是把两个元素“连接”起来，连接的关系是具有传递、对称性的
例如最开始有1, 2, 3, 4, 5这五个元素
我们连接1和2，再连接3和4，这时isConnected(2, 4)就是false而isConnected(1, 2)就是true
这时再连接2和3，那么isConnected(1, 4)也会是true

2 QuickFind

记录谁和谁连在一起是很麻烦的，事实上，只需要记录它们是不是在同一个集合里就好了，判断两个元素是否连接时，只需要判断它们是不是在一个集合里就可以了
我们用一个整数数组来记录

• The indices of the array represent the elements of our set.

• The value at an index is the set number it belongs to.

例如，{0, 1, 2, 4}, {3, 5}, {6}用数组表示就是[4, 4, 4, 5, 4, 5, 6]，当然，4, 5, 6数字是无所谓的，只需要保证同一个集合里的元素的值是同一个就可以了，这时如果connect(3, 2)，就变成[4, 4, 4, 4, 4, 4, 6]

public class QuickFindDS implements DisjointSets {

    private int[] id;

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

    /** Need to iterate through the array => Θ(N) */
    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;
            }
        }
    }

    /** Θ(1) */
    public boolean isConnected(int p, int q) {
        return (id[p] == id[q]);
    }
}

这样的实现，判断是否连接是非常快的，但是连接时，必须遍历整个数组以确保找到所有满足id[i] == pid的元素

3 Quick Union

Suppose we prioritize making the connect operation fast. We will still represent our sets with an array. Instead of an id, we assign each item the index of its parent. If an item has no parent, then it is a ‘root’ and we assign it a negative value.

This approach allows us to imagine each of our sets as a tree. For example, we represent {0, 1, 2, 4}, {3, 5}, {6} as:

public class QuickUnionDS implements DisjointSets {
    private int[] parent;

    /** All elements are roots at first. */
    public QuickUnionDS(int num) {
        parent = new int[num];
        for (int i = 0; i < num; i++) {
            parent[i] = -1;
        }
    }

    /** Find the root of element p. */ 
    private int find(int p) {
        while (parent[p] >= 0) {
            p = parent[p];
        }
        return p;
    }

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

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

这样，构造并查集时，我们要遍历数组，时间复杂度是$\Theta (N)$

判断是否连接时，我们考虑最坏情况，整个并查集变成了一个斜的树，这时由于find需要$\Theta (N)$的时间，而connect或判断任何两个元素是否connected都需要find

因此，这种实现下，connect和isConnected的复杂度都是$O(N)$，不过这只是一个上界，如果我们的树是平衡的，那么这两个操作并不是每次都需要$\Theta (N)$的复杂度的

4 Weighted Quick Union

我们看到，主要限制我们时间的是find，如果元素在这个代表着集合的“树”的底部的话，我们希望树越矮越好，这样find就越快

所以，进行connect时，在合并两棵树的时候，我们希望合并完的树要尽量矮，我们把矮的树挂在高的树的根下面，这样，合并后至少树的高度不会增加，除非两棵树高度一致，那么树的高度会+1

不过下面我们应用的合并法则是，合并两棵树时，把所含元素数量少的树挂在所含元素数量多的树的根下面，这两种操作最后的复杂度都是相差不大的，而这种记录数量的方法，代码会更简单，详情可以见我之前的笔记

每个根的数值我们不再用-1来记录，而是这个集合（或这棵树）所含元素的数量的相反数

public class QuickUnionDS implements DisjointSets {
    private int[] parent;

    /** All elements are roots at first. */
    public QuickUnionDS(int num) {
        parent = new int[num];
        for (int i = 0; i < num; i++) {
            parent[i] = -1;
        }
    }

    /** Find the root of element p. */ 
    private int find(int p) {
        while (parent[p] >= 0) {
            p = parent[p];
        }
        return p;
    }

    @Override
    public void connect(int p, int q) {
        int i = find(p);
        int j= find(q);
        if (parent[i] < parent[j]) {
            parent[i] += parent[j];
            parent[j] = i;
        } else {
            parent[j] += parent[i];
            parent[i] = j;
        }
    }

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

我们来考虑最坏情况下树的高度是多少，这决定了connect和isConnected运行时间的上限，如果一棵树有$N$个元素的话，它的高度最高是多少呢，可不要回答是$N-1$噢（如果一个结点的话我们认为高度是0），因为这次我们在合并树时有了条件限制

我们考虑最坏情况下树的高度。设单个节点形成的树高度为 $0$。

对于按高度合并，只有当两棵高度相同的树合并时，新树的高度才会增加 $1$。因此，要构造高度为 $1$ 的树，至少需要两个节点；要构造高度为 $2$ 的树，必须至少有两棵高度为 $1$ 的树，因此至少需要 $4$ 个节点；同理，要构造高度为 $H$ 的树至少需要$2^H$个节点。

对于按大小合并，虽然高度增加的方式不完全相同，但可以从单个节点出发分析：一个节点每当深度增加 $1$，说明它所在的树被挂到了另一棵大小至少与它相同的树下面，因此合并后它所在集合的大小至少翻倍。于是一个节点深度达到 $H$ 时，其所在集合至少含有 $2^H$ 个节点。

因此无论按大小还是按高度合并，都有$2^H\le N,$所以

$$H\le\lfloor\log_2N\rfloor$$

因此，find 为 $O(log\ N)$，而 connect 和 isConnected 调用常数次 find，所以也是 $O(log\ N)$

不过，在没有路径压缩的情况下，按高度合并肯定是更好的，而且似乎也没有复杂到哪里去吧

但是加入路径压缩后，精确的高度就变得难以维护，只能有一个大概的"rank"来表征树的高度或用于判断合并，这时size不光更简单还含有这个集合有多少个元素的信息，这或许是它的优势之处

@Override
public void connect(int p, int q) {
    int i = find(p);
    int j= find(q);
    if (parent[i] < parent[j]) {
        parent[j] = i;
    } else if (parent[j] < parent[i]) {
        parent[i] = j;
    } else {
        parent[i] -= 1;
        parent[j] = i;
    }
}

5 Weighted Quick Union with Path Compression

The clever insight is realizing that whenever we call find(x) we have to traverse the path from x to root. So, along the way we can connect all the items we visit to their root at no extra asymptotic cost.

Connecting all the items along the way to the root will help make our tree shorter with each call to find.

Recall that both connect(x, y) and isConnected(x, y) always call find(x) and find(y). Thus, after calling connect or isConnected enough, essentially all elements will point directly to their root.

By extension, the average runtime of connect and isConnected becomes almost constant in the long term! This is called the amortized runtime(均摊运行时间).

/** Find the root of element p with path compression. */ 
private int find(int p) {
    int root = p;
    int next;
    while (parent[root] >= 0) {
        // Find the root.
        root = parent[root];
    }

    for (int trail = p; trail != root; trail = next) {
        // Along the trail, let every item point to the root.
        next = parent[trail];
        parent[trail] = root;
    }
    return root;
}