【譯】Swift算法俱樂部-並查集

iOS開發2019-09-13 10:02:10

黑客技術
點擊右側關注,瞭解黑客的世界!

Java開發進階
點擊右側關注,掌握進階之路!

Python開發
點擊右側關注,探討技術話題!


作者丨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)

並查集是一種數據結構,可以跟蹤一組元素,它們分佈在幾個不相交(非重疊)子集合中。它也被稱為不相交集數據結構。
這是什麼意思呢?例如,並查集數據結構可以跟蹤以下集合:


[ a, b, f, k ]
[ e ]
[ g, d, c ]
[ i, j ]

這些集合是不相交的,因為它們沒有共同的成員。

並查集支持三個基本操作:

  1. Find(A):確定元素A所在的子集。例如,find(d)將返回子集[ g, d, c ]
  2. Union(A, B):將包含 A B 的兩個子集合併為一個子集。例如,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 UnionFindT: 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] = 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. 我們返回根節點的索引作為結果。

這是我説明的意思。現在樹看起來像這樣:





我們調用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] // 3
                    parent[firstSet] = secondSet      // 4
                    size[secondSet] += size[firstSet] // 5
                } else {
                    parent[secondSet] = firstSet
                    size[firstSet] += size[secondSet]
                }
            }
        }
    }

下面是它的工作原理:

  1. 我們找到每個元素所屬的集合。請記住,這給了我們兩個整數:parent數組中根節點的索引。
  2. 檢查這些集合是否相等,如果相等,合併就沒有意義。
  3. 這是大小優化的來源(加權)。我們希望保持樹儘可能淺,所以我們總是將較小的樹附加到較大樹的根部。為了確定哪個是較小的樹,我們按照它們的大小比較樹。
  4. 這裏我們將較小的樹附加到較大樹的根部。
  5. 更新較大樹的大小,因為它只添加了一堆節點。

插圖可能有助於更好地理解這一點。假設我們有這兩個集合,每個都有自己的樹:





現在我們調用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


UnionFind
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 timeAlgorithm
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://hk.wxwenku.com/d/201373588