本文是对 Swift Algorithm Club 翻译的一篇文章。
Swift Algorithm Club是 raywenderlich.com网站出品的用Swift实现算法和数据结构的开源项目,目前在GitHub上有18000+⭐️,我初略统计了一下,大概有一百左右个的算法和数据结构,基本上常见的都包含了,是iOSer学习算法和数据结构不错的资源。
🐙andyRon/swift-algorithm-club-cn是我对Swift Algorithm Club,边学习边翻译的项目。由于能力有限,如发现错误或翻译不妥,请指正,欢迎pull request。也欢迎有兴趣、有时间的小伙伴一起参与翻译和学习🤓。当然也欢迎加⭐️,🤩🤩🤩🤨🤪。
本文的翻译原文和代码可以查看🐙swift-algorithm-club-cn/Union-Find
并查集(Union-Find)
并查集是一种数据结构,可以跟踪一组元素,它们分布在几个不相交(非重叠)子集合中。 它也被称为不相交集数据结构。
这是什么意思呢? 例如,并查集数据结构可以跟踪以下集合:
[ 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算法的有效版本,以查找图的最小生成树。
实施
并查集可以通过多种方式实现,但我们将看一个高效且易于理解的实现:Weighted Quick Union。
PS:并查集 的多个实现已包含在playground .
public struct UnionFind<T: Hashable> {
private var index = [T: Int]()
private var parent = [Int]()
private var size = [Int]()
}
我们的并查集数据结构实际上是一个森林,其中每个子集由树表示。
基于我们的目的,我们只需要跟踪每个树节点的父节点,而不是子节点。 为此,我们使用数组parent
,那么parent[i]
是节点i
的父节点索引。
示例:如果parent
看起来像这样,
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操作实际上返回了set的标签,而不是其内容。
请注意,根节点的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,因为它只包含一个元素。 我们将在Union操作中使用size
数组。
查找
通常我们想确定我们是否已经有一个包含给定元素的集合。 这就是Find操作所做的。 在我们的UnionFind
数据结构中,它被称为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
}
}
因为我们正在处理树结构,所以这边使用的是递归方法。
回想一下,每个集合由树表示,并且根节点的索引用作标识集合的数字。 我们将找到我们要搜索的元素所属的树的根节点,并返回其索引。
-
首先,我们检查给定索引是否代表根节点(即“父”指向节点本身的节点)。 如果是这样,我们就完成了。
-
否则,我们以递归方式在当前节点的父节点上调用此方法。然后我们做了一个非常重要的事情:我们用根节点的索引覆盖当前节点的父节点,实际上将节点直接重新连接到树的根节点。下次我们调用此方法时,它将执行得更快,因为树的根路径现在要短得多。 如果没有这种优化,这种方法的复杂性就是O(n),但现在结合尺寸优化(在Union部分中说明)它几乎是O(1)。
-
我们返回根节点的索引作为结果。
这是我说明的意思。 现在树看起来像这样:
BeforeFind我们调用setOf(4)
。 要找到根节点,我们必须首先转到节点2
然后转到节点7
。 (元素的索引标记为红色。)
在调用setOf(4)
期间,树被重组为如下所示:
现在如果我们需要再次调用setOf(4)
,我们就不再需要通过节点2
再到根节点了。 因此,当您使用Union-Find数据结构时,它会优化自身。 太酷了!
还有一个辅助方法来检查两个元素是否在同一个集合中:
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
}
}
这会调用setOf()
,也会优化树。
Union (Weighted)
最后的操作是 Union,它将两集合并为一组更大的集合。
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
数组中根节点的索引。 -
检查这些集合是否相等,如果相等,合并就没有意义。
-
这是大小优化的来源(加权)。我们希望保持树尽可能浅,所以我们总是将较小的树附加到较大树的根部。为了确定哪个是较小的树,我们按照它们的大小比较树。
-
这里我们将较小的树附加到较大树的根部。
-
更新较大树的大小,因为它只添加了一堆节点。
插图可能有助于更好地理解这一点。 假设我们有这两个集合,每个都有自己的树:
BeforeUnion现在我们调用 unionSetsContaining(4, and:3)
。 较小的树与较大的树相连:
请注意,因为我们在方法的开头调用setOf()
,所以在该过程中也对树进行了优化 - 节点3
现在直接挂在根之上。
具有优化的Union只需要几乎 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个对象
Data Structure | Union | Find |
---|---|---|
Quick Find | N | 1 |
Quick Union | Tree height | Tree height |
Weighted Quick Union | lgN | lgN |
Weighted Quick Union + Path Compression | very close, but not O(1) | very close, but not O(1) |
在N个对象上处理M的union命令
Algorithm | Worst-case time |
---|---|
Quick Find | M N |
Quick Union | M N |
Weighted Quick Union | N + M lgN |
Weighted Quick Union + Path Compression | (M + N) lgN |
扩展阅读
有关如何使用此便捷数据结构的更多示例,请参阅 playground。
作者:Artur Antonov ,Yi Ding
翻译:Andy Ron
校对:Andy Ron
网友评论