【译】Swift算法俱乐部-并查集
点击右侧关注，了解黑客的世界！
点击右侧关注，掌握进阶之路！
点击右侧关注，探讨技术话题！
作者丨Artur Antonov ，Yi Ding
翻译丨Andy Ron
校对丨Andy Ron
本文是对 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
GitHub地址：
https://github.com/andyRon/swift-algorithm-club-cn/tree/master/Union-Find
并查集(Union-Find)
并查集是一种数据结构，可以跟踪一组元素，它们分布在几个不相交（非重叠）子集合中。它也被称为不相交集数据结构。
这是什么意思呢？例如，并查集数据结构可以跟踪以下集合：
这些集合是不相交的，因为它们没有共同的成员。
并查集支持三个基本操作：
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 .
我们的并查集数据结构实际上是一个森林，其中每个子集由树表示。
基于我们的目的，我们只需要跟踪每个树节点的父节点，而不是子节点。为此，我们使用数组parent，那么parent[i]是节点i的父节点索引。
示例：如果parent看起来像这样，
然后树结构看起来像：
这片森林中有两棵树，每棵树对应一组元素。（注意：由于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()：
这会在index字典中查找元素的索引，然后使用辅助方法来查找此元素所属的集合：
因为我们正在处理树结构，所以这边使用的是递归方法。
回想一下，每个集合由树表示，并且根节点的索引用作标识集合的数字。我们将找到我们要搜索的元素所属的树的根节点，并返回其索引。
首先，我们检查给定索引是否代表根节点（即“父”指向节点本身的节点）。如果是这样，我们就完成了。
否则，我们以递归方式在当前节点的父节点上调用此方法。然后我们做了一个非常重要的事情：我们用根节点的索引覆盖当前节点的父节点，实际上将节点直接重新连接到树的根节点。下次我们调用此方法时，它将执行得更快，因为树的根路径现在要短得多。如果没有这种优化，这种方法的复杂性就是O(n)，但现在结合尺寸优化（在Union部分中说明）它几乎是O(1)。
我们返回根节点的索引作为结果。
这是我说明的意思。现在树看起来像这样：
我们调用setOf(4)。要找到根节点，我们必须首先转到节点2然后转到节点7。（元素的索引标记为红色。）
在调用setOf(4)期间，树被重组为如下所示：
现在如果我们需要再次调用setOf(4)，我们就不再需要通过节点2再到根节点了。因此，当您使用Union-Find数据结构时，它会优化自身。太酷了！
还有一个辅助方法来检查两个元素是否在同一个集合中：
这会调用setOf()，也会优化树。
Union (Weighted)
最后的操作是 Union，它将两集合并为一组更大的集合。
下面是它的工作原理：
我们找到每个元素所属的集合。请记住，这给了我们两个整数：parent数组中根节点的索引。
检查这些集合是否相等，如果相等，合并就没有意义。
这是大小优化的来源（加权）。我们希望保持树尽可能浅，所以我们总是将较小的树附加到较大树的根部。为了确定哪个是较小的树，我们按照它们的大小比较树。
这里我们将较小的树附加到较大树的根部。
更新较大树的大小，因为它只添加了一堆节点。
插图可能有助于更好地理解这一点。假设我们有这两个集合，每个都有自己的树：
现在我们调用unionSetsContaining(4, and:3)。较小的树与较大的树相连：
请注意，因为我们在方法的开头调用setOf()，所以在该过程中也对树进行了优化 - 节点3现在直接挂在根之上。
具有优化的Union只需要几乎 O(1) 时间。
路径压缩
路径压缩有助于保持树非常平坦，因此查找操作可能只需要__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命令
| Worst-case time | Algorithm |
Quick Find |
M N |
Quick Union |
M N |
Weighted Quick Union |
N + M lgN |
Weighted Quick Union + Path Compression |
(M + N) lgN |
扩展阅读
有关如何使用此便捷数据结构的更多示例，请参阅 playground。
并查集的*
https://en.wikipedia.org/wiki/Disjointset_data_structure
推荐↓↓↓
长
按
关
注
?【16个技术公众号】都在这里！
涵盖：程序员大咖、源码共读、程序员共读、数据结构与算法、黑客技术和网络安全、大数据科技、编程前端、Java、Python、Web编程开发、Android、iOS开发、Linux、数据库研发、幽默程序员等。
万水千山总是情，点个 “在看” 行不行
本文地址：https://blog.csdn.net/olsQ93038o99S/article/details/100611858