Garland +

Algorithms by Princeton

Union-Find

并查集是一种用于解决所谓的动态连通性问题的算法,主要包括两个算法:快速查找和快速合并, 以及这些算法的一些实现和改进。

开发有效算法的流程:

Dynamic Connectivity

问题描述:Given a set of N objects.

如下图:

path-connection

定义连接

假设“连接到”是一个等价关系,则有:

当有了一个等价关系后,一个对象和连接的集合就分裂为子集,这些子集叫连通分量(Connected components)。连通分量是互相连接的对象 的最大集合。(感觉像是在复习离散数学)

connected-components

如上图就有三个连通分量。连通分量具有如下性质:

这个算法通过维护连通分量来获得效率,并使用连通分量来高效地应答接收到的请求。

实现操作

union

如上图就变成了两个分量

快速查找

属于一种贪心算法,数据结构如下:

search

如上图,查找的操作就变成了查看 是不是相同的值。Union 操作就是把其中一个对象 所在的分量对应的值变成另一个对象所在分量对应的值,不过当对象数目很大时会出现一些问题,因为需要改变很多值。

算法 Demo 如下(课程给的示例是 Java,这里用 python 实现):


class QuickFindUF():

    def __init__(self, n):
        self.ids = list(range(n))

    def is_connected(self, p, q):
        return self.ids[p] == self.ids[q]

    def union(self, p, q):
        if self.is_connected(p, q):
            return
        pid = self.ids[p]
        qid = self.ids[q]
        for index, v in enumerate(self.ids):
            if v == pid:
                self.ids[index] = qid

算法分析

只考虑对数组的访问的话,初始化和合并操作都要遍历一次数组,也就是 的复杂度,查找只用一次操作, 所以是常数级的复杂度。可以发现,合并操作开销太大,特别是如果需要在N个对象上进行N次合并操作的时间复杂度是 , 对于大型问题是不能接受平方时间的算法的,因为在于它们无法成比例适应大规模问题。

快速合并

使用的是“懒策略”,即尽量避免计算直到不得不进行计算

Blog

Thoughts

Project