并查集(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
