初识并查集

API

并查集需要实现以下两个功能：

  • connect(x, y)：将 x 与 y 连通。
  • isConnected(x, y)：判断 x 与 y 是否连通。

这里所说的“连通”具有如下三个性质：
1、自反性：x 和 x 是连通的。
2、对称性：如果 x 和 y 连通，那么 y 和 x 也连通。
3、传递性：如果 x 和 y 连通，y 和 z 连通，那么 x 和 z 也连通。

如：

为了简化我们的实现，我们先：

  • 强制所有元素都为整数；
  • 提前声明好并查集中元素的数目，且所有元素之间无连接。

与 List 一样，我们先提供一个用户调用的接口 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);
}

我们的目标是设计一个高效的并查集实现：

  • 元素数量非常多时仍能快速操作；
  • 方法调用次数非常多时仍能快速操作；
  • 方法的调用是交叉的，而非按照固定顺序调用。

追踪连通分量

我们看着图就能分辨出哪两个元素之间是连通的，但计算机是无法在底层为我们绘制一幅一模一样的图的，所以也许我们可以：

  • 连通两个元素时，将每一条连接起来的线存储起来；
  • 检查连通性时，用某种迭代来遍历每条线来检查一个元素能否到达另一个元素。

光读这些文字都开始头大了。事实上，这种方法真实现起来也是非常慢的。我们需要一种更好的思路。

这张图不知怎的会有一种感觉，0、1、2、4 是一组，3、5 是一组，6 是一组，同组中的元素之间相互连通，不同组中的元素之间没有连接。这个思路怎么样呢？

这个想法似乎是可行的，让我们尝试实现！

实现并查集

接下来的问题是如果我想实际编写这个程序，我的并查集对象必须有哪些实例变量来在内存中追踪这些东西呢？

List of Sets

思路一：集合列表

用一个集合来表示一个组，再用一个列表来存储这些集合，如：[{0, 1, 2, 4}, {3, 5}, {6}]。用 Java 表示就是 List<Set<Integer>>。

但如果我们用上一节的渐近工具检查一下就会发现这种方法是很慢的：

最开始时每个元素都是单独的一个集合，这意味着我们如果要查找一个元素就需要从头开始遍历集合，最坏的情况就是从头遍历到尾，消耗的时间将是 Θ(N)\Theta(N)。如果并查集中有成千上万个元素，这将是非常慢的。

当然这只是最坏的情况，也有可能只需要查找第一个或是第二个元素，花费的时间就不需要这么多，所以我们用 O(N)O(N) 来表示花费的时间，这意味着这个操作花费时间随着输入大小的增长阶是小于等于 NN 的。

Quick Find

思路二：整型数组

我们利用一个数组，数组下标代表并查集元素的值，当两个组连通时，将两个组中所有元素对应的数组元素的值置为相同。

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

这样 isConnected(p, q) 就会直接比较 id[p] 与 id[q] 是否相等而不需要遍历了，无论并查集中有多少元素，这个操作都只花费常数时间，非常快！

但如果我们 connect(p, q)，就需要将 p 所在组中对应的所有数组元素的值置为与 q 对应的值相等，这就又需要遍历了。有没有更好的方法？

Quick Union

上个思路的 isConnected 很快，但 connect 很慢，本质上是因为 connect 在合并两个集合时需要修改其中一个集合的每个元素对应的数组中的值。我们能不能只修改一个值就实现两个集合的合并？

思路三：分配父项

为每个元素都分配一个父项，最终会形成一个树形结构：

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 findParent(int p) {
        while (parents[p] >= 0) {
            p = parents[p];
        }
        return p;
    }

    @Override
    public void connect(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        parent[ap] = bp;
    }

    @Override
    public boolean isConnected(int a, int b) {
        return findParent(a) == findParent(b);
    }
}

每个元素对应数组的值不再是一个统一的数而是它父项的值。“-1”则代表它是这个集合的“根”。

那么具体应该怎样合并两个集合呢？假设我们要 connect(5, 2)，我们不能直接修改 5 的父项为 2 因为这样 5 和 3 之间就会断连。我们应该分别追溯到 5 和 2 的根，再将 5 的根（也就是 3）连接到 2 的根（也就是 0）上。

但比起上一种方法，这种方法有一个潜在的问题是：我们不得不爬一棵树。

  • connect() 需要爬到根节点以合并两棵树；
  • isConnected() 需要爬到根节点以判断两个元素的根是否相同。

如果我们有这么一棵树，那最坏情况消耗的时间又回到了第一种方法：

如何避免构造出这么一棵参天大树呢？

Weighted Quick Union

思路四：加权快速联合

在对两棵树进行合并时，我们将增加一个比较的步骤：

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

    public WeightedQuickUnionDS(int N) {
        parent = new int[N];
        for (int i = 0; i < N; ++i) {
            parent[i] = -1;
        }
    }

    private int findParent(int p) {
        while (parents[p] >= 0) {
            p = parents[p];
        }
        return p;
    }

    @Override
    public void connect(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        if (ap == bp) return;  // 已经在同一集合中，直接返回

        if (parent[ap] <= parent[bp]) {  // ap的集合更大或相等
            parent[ap] += parent[bp];
            parent[bp] = ap;
        } else {
            parent[bp] += parent[ap];
            parent[ap] = bp;
        }
    }

    @Override
    public boolean isConnected(int a, int b) {
        return findParent(a) == findParent(b);
    }
}

显然 A 方法要比 B 好，因为 A 生成的树高度为 2，而 B 生成的树高度为 3。因此在将两棵树合并前，需要先比较两棵树的大小，再将小树合并到大树的根节点上，这样就能保证较大的树不会被较小的树“抬高”。

思路我们明确了，我们该如何存储并比较每棵树的大小呢？有两个方法：

  • 因为根节点对应数组元素的值只利用了符号，没有利用大小，因此我们可以用 -weight 来代替 -1，如：parent[a] = -4 表示以 a 为根节点的树共有 4 个节点；
  • 另外创建一个数组来存储每棵树的大小。

显然方法 1 是更好的。

现在再让我们来分析一下此时的时间复杂度吧，想象一下树的高度随着节点增加而增长的最快方式：

1 个节点时高度为 0

2 个节点时高度为 1

3 个节点不可能构造出更高的树

至少需要另一棵节点数相同的树才能使高度增加，此时共有 4 个节点

同理至少 8 个节点才能使树高度再次增加

最终我们可以得到这个表格：

节点数 N 高度 H
1 0
2 1
4 2
8 3
16 4

已知 QuickUnion 的运行速度与树的高度有关：O(H)O(H)，树的高度又依据节点数决定：H=O(log⁡N)H = O(\log N)，所以 connect 和 isConnected 都是 O(log⁡N)O(\log N)。

细心的同学可能发现：我们以上都是基于树的节点数进行比较合并，为什么不专门针对树的高度呢？

没错，这样确实会让树的高度增加地更缓慢，但按照最坏情况进行时间复杂度分析，这两者几乎是一致的，都为 Θ(log⁡N)\Theta(\log N)。而后者在代码实现上会更复杂一些，有兴趣的同学可以尝试实现。

WQU with Path Compression

还有可以优化的地方吗？

听起来有点疯狂，但是有的兄弟，有的。

假如我们想判断 15 和 10 是否连通，我们会先检查 15 的根节点是 0，接着检查 10 的根节点是 0，与 15 的根节点相同，所以连通。但在这期间，不只是 15 和 10，我们还路过了 11、5、1、3 这些节点，这些节点的根节点都必定是 0。如果我们把这些节点都直接绑定到根节点，下次检查这些节点的时候不就不需要再“爬树”了吗？

思路五：带有路径压缩的加权快速联合

public class WQUwithPathCompression implements DisjointSets {
    private int[] parents;

    public WQUwithPathCompression(int N) {
        parents = new int[N];
        for (int i = 0; i < N; ++i) {
            parents[i] = -1;
        }
    }

    public int findParent(int p) {
        if (parents[p] < 0) {
            return p;
        }
        parents[p] = findParent(parents[p]);    // 路径压缩
        return parents[p];
    }

    @Override
    public void connect(int a, int b) {
        int ap = findParent(a);
        int bp = findParent(b);
        if (ap == bp) return;

        if (parents[ap] <= parents[bp]) {
            parents[ap] += parents[bp];
            parents[bp] = ap;
        } else {
            parents[bp] += parents[ap];
            parents[ap] = bp;
        }
    }

    @Override
    public boolean isConnected(int a, int b) {
        return findParent(a) == findParent(b);
    }
}

随着调用 connect 和 isConnected 的次数越来越多，树就会越来越扁平，使用这种数据结构的速度就会越来越快。

这时我们如果再分析一次节点数与树的高度的关系，我们将会得到一个 反阿克曼函数 O(α(N))O(\alpha(N))，它增长得极其缓慢：

NN α(N)\alpha(N)
22 11
44 22
1616 33
6553665536 44
22655362^{2^{65536}} 55

想让树高到 6？你得要比宇宙中原子数量还多的节点 🤯

细心的同学可能会注意到，我们的路径压缩是通过递归的方式实现的，这是否会导致时间复杂度的增加？

其实是不会的。递归调用的时间复杂度是 调用次数 × 每次调用成本：

  • 每次调用 findParent 只会向上跳一个父节点，所以调用成本为 O(1)O(1);
  • 而调用次数只有在第一次查找时为 O(log⁡N)O(\log N) （加权后的树高），路径压缩后，后续调用的次数都为 O(1)O(1)。

均摊下来时间复杂度仍是 O(1)O(1)，或者说 O(α(N))O(\alpha(N))。