I'm trying to implement the union find algorithm using Go. I want to implement different strategies like quick find, quick union and weighted quick union using one structure UnionFind
see below. I put the code into a package unionfind
package unionfind
type Unionfind struct {
elements []int
}
func makeUnionfind(n int) Unionfind {
elements := make([]int, n)
for idx := range elements {
elements[idx] = idx
}
return Unionfind{elements}
}
Next I create the functions for the different strategies starting with quick find
. The example below isn't working. But I have no idea where to put the strategy specific code, how to name the package and how to import the common structure type.
// create a separate package for each strategy?
package quickfind
// import the structure locally?
import ufp "./unionfind"
// prefer methods over functions for convenience?
func (uf *ufp.Unionfind) union(a int, b int) {
aroot := uf.elements[a]
broot := uf.elements[b]
for k, v := range uf.elements {
if v == aroot {
uf.elements[k] = broot
}
}
}
func (uf *ufp.Unionfind) connected(a int, b int) bool {
return uf.elements[a] == uf.elements[b]
}
How should I organize my code the get the quick find algorithm working but have the UnionFind
structure separated?