[译] Swift 算法学院 - 并查集
本篇是来自 Swift 算法学院的翻译的系列文章,Swift 算法学院 致力于使用 Swift 实现各种算法,对想学习算法或者复习算法的同学非常有帮助,讲解思路非常清楚,每一篇都有详细的例子解释。 更多翻译的文章还可以查看这里。
并查集
并查集数据结构是对一组分成多个不相交的子集元素的处理,并查集又称为不相交集。
到底是神马意思?举个例子,并查集是用来处理下面集合合并和查询:
[ a, b, f, k ] [ e ] [ g, d, c ] [ i, j ] 复制代码
这些集合是不相交的,因为它们没有共同的成员。
并查集支持三种基本操作:
- Find(A):找到 A 在那个子集中。比如 find(d) 函数返回 [g, d, c ] 。
- Union(A, B):把某两个集合 A 和 B 合成一个子集。比如 union(d, j) 需要将 [ g, d, c ]和 [ i, j ] 合并成一个大的集合[ g, d, c, i, j ]。
- AddSet(A):生成一个只包含 A 新子集。如 addSet(h) 生成一个新集合 [ h ]。
该数据结构最常用于查询无向图中的节点。它也能用于提高 Kruskal 算法的效率,用于查找图中最小生成树。
代码实现
并查集有很多实现方法,下面用一种相对简单高效的方式实现:加权Quick-Union。
PS:可以在 playground 中找到并查集的多种实现方式
public struct UnionFind<T: Hashable> { private var index = [T: Int]() private var parent = [Int]() private var size = [Int]() } 复制代码
这里并查集数据结构实际是森林,每个子集用树表示。
由于目标只是保持对每个树节父点的联系,不需要联系子节点,可以通过一个父节点的数组来表示,parent[ i ] 表示第 i 个父节点。
举例:如果父节点数组像这样
parent [ 1, 1, 1, 0, 2, 0, 6, 6, 6 ] i 0 1 2 3 4 5 6 7 8 复制代码
树的结构如下:
1 6 / \ / \ 0 2 7 8 / \ / 3 5 4 复制代码
森林中有两棵树,每棵对应一组元素集合。(备注:这里是因为受制于 ASCII 表达形式所以用二叉树表示的,实际情况并不局限于此)。
每个子集使用唯一的数字来标示。子集合树的根节点作为索引,如 1 是第一棵树的根节点, 6 是第二棵树的根节点。
在这个例子中有两个子集,第一个代表值为 1 ,第二个为 6 。Find 函数返回的是子集的代表值,而不是它的内部数据。
注意 parent[] 中根节点指向自己,如 parent[1] = 1 和 parent[6] = 6 ,可以通过这个方法可以发现那些是根节点。
添加
从添加开始,看看如何实现一些基本操作:
public mutating func addSetWith(_ element: T) { index[element] = parent.count // 1 parent.append(parent.count) // 2 size.append(1) // 3 } 复制代码
当添加一个新元素,实际是添加一个包含该元素的集合。
- 保存新元素的索引到 index 字典中。可以帮助快速查找该元素。
- 添加索引到 parent 数组中并为这个集合新建一个树。由于这个新集合只包含一个值,而且该值为树的根节点,所以parent[i] 指向自己。
- size[i] 是索引值为 i 根节点处的节点个数。对于新集合因为只含一个元素所以值为 1 。在随后的合并操作中会用到 size 这个数组。
查找
经常需要查找某个元素是否在集合中, Find 函数就是干这个事滴!在 并查集 中又称为 setof():
public mutating func setOf(_ element: T) -> Int? { if let indexOfElement = index[element] { return setByIndex(indexOfElement) } else { return nil } } 复制代码
先通过 index 字典来查找某个元素的索引值,再用一个函数来查找该元素属于哪个集合:
private mutating func setByIndex(_ index: Int) -> Int { if parent[index] == index { // 1 return index } else { parent[index] = setByIndex(parent[index]) // 2 return parent[index] // 3 } } 复制代码
既然和树打交道了就用递归的方法来解决吧。
回顾一下,每个集合用一棵树来表示,根节点的索引值为集合的代表值。查找该元素所属树的根节点,并返回它的索引值。
- 第一步先检查输入的 index 值是否是根节点。(根节点的 parent 指回自己),如果是,结束查找。
- 否则,递归调用当前节点的父节点方法。 接下来的是非常重要的一步:重写当前节点的父节点为根节点,实际就是将节点重新连接到根节点上。当下次在调用这个方法的时候速度就快了,因为到根节点的路径非常短了。如果没有这个优化这个方法的复杂度为 O(n),但经过路径压缩后(在合并环节)复杂度接近 O(1)。
- 返回根节点作为结果。
这里有一个图形化的解释,让我们来看看:
调用 setOf(4) 试试看,为了查到根节点,需要先访问 2 节点,然后再访问 7 节点。(索引值用红色数字标示)。
调用 setOf(4) 后,树结构如下:
现在若再调用 setOf(4) ,不需要再经过节点 2 才能到根节点。因此在使用并查集数据结构的时候会自优化,是不是很酷!
这里有个便捷的方法可以判断两个元素是不是在一个集合中:
public mutating func inSameSet(_ firstElement: T, and secondElement: T) -> Bool { if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { return firstSet == secondSet } else { return false } } 复制代码
因为调用了 sefOf() 方法也会优化树结构。
合并(按秩的方式)
最后的操作是 合并 就是将两个集合合并成一个大的集合。
public mutating func unionSetsContaining(_ firstElement: T, and secondElement: T) { if let firstSet = setOf(firstElement), let secondSet = setOf(secondElement) { // 1 if firstSet != secondSet { // 2 if size[firstSet] < size[secondSet] { // 3 parent[firstSet] = secondSet // 4 size[secondSet] += size[firstSet] // 5 } else { parent[secondSet] = firstSet size[firstSet] += size[secondSet] } } } } 复制代码
计算过程如下:
- 给出两个集合,这两个集合都有一个根节点的索引值存在 parent 数组中。
- 判断是不是相同的集合,合并两个相同的集合没有任何意义。
- 以秩大小作为权重进行优化,如果想让树的深度尽可能的保持最小,需要把小的树添加到大的树上。通过比较两个树的数组个数决定那个树更小。
- 下面将小一些的树添加到大一些树的根节点。
- 因为增加一堆新的树节点,需要更新大树的元素个数值。
为了更好介绍这个算法,举个例子说明一下,有两个集合,每个集合的树的数据结构如下:
现在调用方法 unionSetsContaining(4, and: 3) 将秩小一些的树添加到大一些的树上:
因为在开始的时候调用了 setOf() ,所以大一些的树仍然会走优化流程 — 节点 3 直接挂到根节点上。
合并的优化的复杂度也为 O(1)。
路径压缩
private mutating func setByIndex(_ index: Int) -> Int { if index != parent[index] { // Updating parent index while looking up the index of parent. parent[index] = setByIndex(parent[index]) } return parent[index] } 复制代码
路径压缩能够使树不断变平坦,因此查找复杂度 几乎 接近 O(1)。
复杂度总结
处理 N 个元素
数据结构UnionFindQuick FindN1Quick UnionTree heightTree heightWeighted Quick UnionlgNlgNWeighted Quick Union + Path Compressionvery close, but not O(1)very close, but not O(1)
N个元素中做M次并集
算法最坏的情况Quick FindM NQuick UnionM NWeighted Quick UnionN + M lgNWeighted Quick Union + Path Compression(M + N) lgN
更多
可以继续查看源码中的其他算法的工作原理。还可以看Union-Find at Wikipedia。
作者Artur Antonov, 审核 Yi Ding . 译者KeithMorning。参考文献:K码农-http://kmanong.top/kmn/qxw/form/home?top_cate=28