Disjoint Set is an algorithm that can help us solve many graph problems. There are many variations/improvements on the base algorithm, but today we will implement the union find by rank and path compression.
Let’s first initialise the arrays:
|
1 2 3 4 5 6 7 8 9 10 11 |
public class UnionFind { var rank: [Int] = [] var root: [Int] = [] public init(size: Int) { for i in 0..<size { root[i] = Array(0..<size) rank[i] = Array(repeating: 1, count: size) } } } |
Next we will work on the find method:
|
1 2 3 4 5 6 7 |
public func find(_ x: Int) -> Int { if x == root[x] { return x } root[x] = find(root[x]) return root[x] } |
We have to make sure we update the root array, while we are searching.
And lastly we will implement the union me
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
public func union(_ x: Int, _ y: Int) { let rootX = find(root[x]) let rootY = find(root[y]) if rootX != rootY { if rank[rootX] < rank[rootY] { root[rootX] = rootY rank[rootY] += rank[rootX] } else { root[rootY] = rootX rank[rootX] += rank[rootY[ } } } |
In this method we have to make sure we update correctly the rank array.
https://github.com/Fragki/Algorithms/blob/main/swift-algo/Sources/swift-algo/swift_algo.swift
