美文网首页swiftswift初见
【译】Swift算法俱乐部-并查集

【译】Swift算法俱乐部-并查集

作者: Andy_Ron | 来源:发表于2019-09-17 11:45 被阅读0次

    本文是对 Swift Algorithm Club 翻译的一篇文章。
    Swift Algorithm Clubraywenderlich.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 ]
    

    这些集合是不相交的,因为它们没有共同的成员。

    并查集支持三个基本操作:

    1. Find(A):确定元素A所在的子集。例如,find(d)将返回子集 [ g, d, c ]

    2. Union(A, B):将包含 AB 的两个子集合并为一个子集。 例如,union(d, j) 表示将 [g, d, c][i, j] 组合成更大的集合 [g, d, c, i, j]

    3. 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,第二个带有标签6Find操作实际上返回了set的标签,而不是其内容。

    请注意,根节点的parent[]指向自身。 所以parent[1] = 1parent [6] = 6。 这就是我们如何判断那些是根节点的方法。

    添加集合

    让我们看一下这些基本操作的实现,从开始添加新集。

    public mutating func addSetWith(_ element: T) {
      index[element] = parent.count  // 1
      parent.append(parent.count)    // 2
      size.append(1)                 // 3
    }
    

    添加新元素时,实际上会添加一个仅包含该元素的新子集。

    1. 我们在index字典中保存新元素的索引。 这让我们可以在以后快速查找元素。

    2. 然后我们将该索引添加到parent数组中,为该集合构建一个新树。这里,parent[i]指向自身,因为表示新集合的树只包含一个节点,当然这是该树的根节点。

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

    因为我们正在处理树结构,所以这边使用的是递归方法。

    回想一下,每个集合由树表示,并且根节点的索引用作标识集合的数字。 我们将找到我们要搜索的元素所属的树的根节点,并返回其索引。

    1. 首先,我们检查给定索引是否代表根节点(即“父”指向节点本身的节点)。 如果是这样,我们就完成了。

    2. 否则,我们以递归方式在当前节点的父节点上调用此方法。然后我们做了一个非常重要的事情:我们用根节点的索引覆盖当前节点的父节点,实际上将节点直接重新连接到树的根节点。下次我们调用此方法时,它将执行得更快,因为树的根路径现在要短得多。 如果没有这种优化,这种方法的复杂性就是O(n),但现在结合尺寸优化(在Union部分中说明)它几乎是O(1)

    3. 我们返回根节点的索引作为结果。

    这是我说明的意思。 现在树看起来像这样:

    BeforeFind

    我们调用setOf(4)。 要找到根节点,我们必须首先转到节点2然后转到节点7。 (元素的索引标记为红色。)

    在调用setOf(4)期间,树被重组为如下所示:

    AfterFind

    现在如果我们需要再次调用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]
                    }
                }
            }
        }
    

    下面是它的工作原理:

    1. 我们找到每个元素所属的集合。请记住,这给了我们两个整数:parent数组中根节点的索引。

    2. 检查这些集合是否相等,如果相等,合并就没有意义。

    3. 这是大小优化的来源(加权)。我们希望保持树尽可能浅,所以我们总是将较小的树附加到较大树的根部。为了确定哪个是较小的树,我们按照它们的大小比较树。

    4. 这里我们将较小的树附加到较大树的根部。

    5. 更新较大树的大小,因为它只添加了一堆节点。

    插图可能有助于更好地理解这一点。 假设我们有这两个集合,每个都有自己的树:

    BeforeUnion

    现在我们调用 unionSetsContaining(4, and:3)。 较小的树与较大的树相连:

    AfterUnion

    请注意,因为我们在方法的开头调用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 AntonovYi Ding
    翻译:Andy Ron
    校对:Andy Ron

    相关文章

      网友评论

        本文标题:【译】Swift算法俱乐部-并查集

        本文链接:https://www.haomeiwen.com/subject/vggoyctx.html