并查集(Union Find)

并查集也叫做不相交集合（Disjoint Set）,这种数据结构主要用来快速的判断两个集合是否有交集的问题，或者说判断两个点是否有连接的问题。并查集有两个核心操作：

1，查找(Find)：查找元素所在的集合。
2，合并(Union)：将两个元素所在的集合合并为一个集合。
常见的实现思路有两个，分别为Quick Find,QuickUnion

快速查找（Quick Find）

快速查找的union操作是：将一个集合的的元素，全部移到另一个集合中。
我们将判断的对象，抽象为整型数字，例如，我们有7个对象，将其抽象为（0～6）7个数字，我们用整型数组来存储数据，将数字表示其所在集合的索引值，数组的值里面表示其所在的集合。

unionFind1.png

数组的容量为 7，一开始 0～6互不相连，分别属于不同的集合，我们依次将它存放在数组中。
接下来，我们将 5 和 6 相行相连,执行union( 5, 6)

unionFind2.png

将索引5处的值，修改为索引 6的值，这样的话，索引 5和6处的值将保持一致，这样 5和6就属于同一个集合。
然后，我们在执行union(5, 4)，将索引5处的集合值取出，并且将所有该集合的值，修改为索引4 处的集合值，这样的话，4，5，6就同属于一个集合。

unionFind3.png

最后，我们执行union( 2, 1)，将索引2处的集合值取出，并将数组中所有的该集合值替换为索引1处的索引值。

unionFind4.png

经过以上合并之后，我们可以看到 1和2 属于同一个集合，4、5、6属于同一个集合。

unionFind5.png

实现

首先我们来看下，并查集需要实现哪些协议

 protocol UnionFindProtocol {
    var parents: [Int] { get set } // 1

    init(capacity: Int) // 2
    // 查找v所属的集合
    func find(_ v: Int) -> Int? // 3
    // 合并 v1、v2所在的集合
    func union(_ v1: Int, _ v2: Int) // 4
    // 是否在同一个集合
    func isSame(_ v1: Int, _ v2: Int) -> Bool // 5

    func rangeCheck(_ i: Int) -> Bool // 6




}

extension UnionFindProtocol {
    func isSame(_ v1: Int, _ v2: Int) -> Bool {

        return find(v1) == find(v2)                 // 7
    }

    func rangeCheck(_ i: Int) -> Bool {
        
        return i < parents.count                    // 8
    }
}

1，存放整型数据的数组。
2，并查集类必须实现的初始化方法。
3，查找v 所属的集合的协议方法。
4，合并两个点。
5，判断两个点是否在同一个集合。
6，检测数组是否越界。
7，在协议的扩展里面增加是否在同一个集合里面的默认实现。
8，增加检测是否数组越界的默认实现。

我们新建QuickFind类并遵守 UnionFindProtocol协议，并实现其协议方法

class QuickFind: UnionFindProtocol {
    var parents: [Int]

    // 父节点就是根节点
    func find(_ v: Int) -> Int? {
        guard rangeCheck(v) else {
            return nil
        }

        return parents[v]
    }

    /*
     将v1所在集合的所有元素，都嫁接到v2的父节点上
     */
    func union(_ v1: Int, _ v2: Int) {
        let p1 = find(v1)
        let p2 = find(v2)
        if p1 == p2 {
            return
        }

        // 将 p1 所在集合的里面所有的元素，迁移到 p2 所在集合中
        for(index, item)  in parents.enumerated() {
            if item == p1 {
                parents[index] = p2 ?? -1
            }
        }
    }


    required init(capacity: Int) {
        guard capacity > 0 else {
            parents = [Int]()
            return
        }
        parents = Array(repeating: 0, count: capacity)

        for i in 0..<capacity {
            parents[i] = I
        }
    }

}

最后，我们对QuickFind进行单元测试，新建一个 UnitTest

import XCTest

@testable import DataAndAlgorimTotal

class UnionTest: XCTestCase {

    override func setUp() {
    }

    override func tearDown() {
    }

    func testExample() {.
    }

    func testPerformanceExample() {
        self.measure {
        }
    }

    func testQuickFind() {
        let qf = QuickFind(capacity: 7) // 新建 7 个互不相连的集合
        qf.union(5, 6) // 将 5，6 进行连接
        qf.union(5, 4) // 将 5，4 进行连接
        qf.union(2, 1) // 将 2，1 进行连接
        let oneSame = qf.isSame(5, 6) // true

        let twoSame = qf.isSame(1, 5) // false
        let threeSame = qf.isSame(4, 6) // true

        XCTAssert(oneSame == true && twoSame == false && threeSame == true)
    }
}

在快速查找的实现中，我们在查找 （find） 的时候，是直接根据索引值在数组里面查找，时间复杂度为 O(1) ,在进行合并（union） 的时候，需要遍历整个数组，时间复杂度为 O(n)

Quick Union(快速合并)

快速合并是并查集的另一种思路，在讲解快速合并时，我们把集合关系抽象为树的关系：子节点的父节点是其所在的集合，该树的根节点是整个节点所在的集合。
快速合并的 union(v1, v2) 操作是将让 v1 所在集合的所有元素都指向 v2 的根节点。

Union(合并)

假定我们现在有7个元素，索引为 0 ~ 6，数组每一个索引处分别存放根节点，代表其所在的集合。

quickUnion1.png

1，圆圈代表是根节点。
2，元素 0 ~ 6，分别属于 7个不同的集合。

接下来，当我们执行 union(1, 0)时，就是索引 0的跟节点，设置为 1 的根节点。换句话说，将节点 1 的父节点为节点0，将索引1处的根节点设置为索引 0 处的根节点。

quickunion2.png

1，索引1 的父节点为索引0处的节点，索引0的父节点为索引0，此时，0 和 1同属一个集合且该集合只有这两个元素。

接下来我们执行 union(1, 2)时，将索引2处的跟节点设置为索引 1的根节点。 1 的根节点是 0，索引要将 0的父节点设置为 2。

quickUnion3.png

从上图的数组中（蓝色部分）我们可以看出 1的父节点为 0，0的父节点为 2，2的父节点为 2，即2为根节点。即 1 -> 0 -> 2，此时，1，0，2同属一个集合，且该集合有且只有3个元素

接下来我们将 3，4进行合并执行union(3, 4)，将索引4的根节点设置为3的根节点，因为索引4的根节点是4，所以将索引3处的跟节点设为4

quickUnion4.png

最后，我们将 3和1进行合并 union(3，1)，将 1个根节点设置为 3的根节点， 1的根节点为 2，3的根节点为 4，所以，将要 4的父节点设为 2。

quickUnion5.png

经过以上合并之后， 0，1，2，3，4就同属于一个集合了。0 和4 的父节点都为 2 。

Find(查找)

经过以上合并之后，当索引值 v = array[v]的时候，表示该出为集合的根节点，当索引值 != array[v]的时候，array[v]则表示该节点父节点的索引。如上图 quickUnion5.png 所示，索引1处的父节点为索引0，索引0的父节点为索引2。

Quick Union 实现

我们新建 QuickUnion类，并遵守UnionFindProtocol

class QuickUnion: UnionFindProtocol {
    var parents: [Int]

    func find(_ v: Int) -> Int? {
        var index = v
        guard rangeCheck(index) else {
            return nil
        }

        // 根节点： 索引值 = parents[索引值]
        while index != parents[index] {
            index = parents[index] // 去父节点里面去找
        }
        return index
    }

    func union(_ v1: Int, _ v2: Int) {
        let p1 = find(v1)  // 查找 v1 的根节点
        let p2 = find(v2) // 查找 v2 的根节点
        if p1 == p2 { return }

        guard let pOne = p1, let pTwo = p2 else {
            return
        }
        parents[pOne] = pTwo // 将v1 的根节点设置为v2的根节点
    }

    required init(capacity: Int) {
        guard capacity > 0 else {
            parents = [Int]()
            return
        }
        parents = Array(repeating: 0, count: capacity)

        for i in 0..<capacity {
            parents[i] = i
        }
    }

}

在 UnionTest里面进行单元测试

    func testQuickUnion() {
        let qf = QuickUnion(capacity: 7)
        qf.union(5, 6)
        qf.union(5, 4)
        qf.union(2, 1)
        let oneSame = qf.isSame(5, 6) // true

        let twoSame = qf.isSame(1, 5) // false
        let threeSame = qf.isSame(4, 6) // true

        XCTAssert(oneSame == true && twoSame == false && threeSame == true)
    }

在 QuickUnion 中 find 方法需要一直沿着父节点找，直到找到父节点位置，查找速度只和集合树的高度有关系，即其时间复杂度为 O(log n)，在 union 方法中，执行了2次 find 和一次数组赋值，其时间复杂度也为 O(log n)

最后附上本文的相关代码DataAndAlgorim