README
¶
UnionFind 
This is an implementation of the UnionFind (disjoint-set) data structure, as described, for example, here: http://algs4.cs.princeton.edu/15uf .
The Union() and Connected() operations take $O(log^* N)$ “log-star” time, which is close to $O(1)$.
Install
$ go get github.com/pietv/unionfind@latest
Example
Using the UnionFind data structure to find the number of “islands” (independent,
disconnected areas of dry land) on a chart.
- The space
- The
.character defines the dry land.
import (
"fmt"
"strings"
"github.com/pietv/unionfind"
)
const chart = `
...... .
. ..
..
.....
.. .
. ..... .
. .
`
// ξ (for ξηρɑ, dry land) is used as a symbol for point.
type ξ struct{ x, y int }
func scan(chart string) int {
var (
lines = strings.Split(chart, "\n")
sets = unionfind.New()
)
for y, line := range lines {
for x := 0; x < len(line); x++ {
if line[x] == '.' {
// Add a standalone piece of land as a disjoint set.
sets.MakeSet(ξ{x, y})
// Union it with a piece of land to the left.
if x > 0 && line[x-1] == '.' {
sets.Union(ξ{x, y}, ξ{x - 1, y})
}
// Union with a piece of land above.
if y > 0 && len(lines[y-1]) > x && lines[y-1][x] == '.' {
sets.Union(ξ{x, y}, ξ{x, y - 1})
}
}
}
}
return sets.Count()
}
For the chart above, the code returns 4 (four islands).
Documentation
¶
Overview ¶
Package unionfind implements a UnionFind (disjoint-set) data structure, as described, for example, here: http://algs4.cs.princeton.edu/15uf .
The Union() and Connected() operations take O(log* N) “log-star” time, which is close to O(1).
The MakeSet() operation when used with multiple arguments, unions elements in one set.
Basic usage:
u := unionfind.New() // Create sets (optional). u.MakeSet(1, 2, 3, 4) // Join them together. u.Union(1, 2) u.Union(3, 4) u.Union(2, 3) // Check if they're connected. fmt.Println(u.Connected(1, 4))
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type UnionFind ¶
type UnionFind struct {
// contains filtered or unexported fields
}
UnionFind maintains sets and a number of connected elements.
func (UnionFind) Connected ¶
Connected returns true if the elements belong to the same set, false otherwise.
func (UnionFind) Find ¶
Find returns the root element of the set. The root element is the same for all elements within the same set.
func (*UnionFind) MakeSet ¶
MakeSet makes an independent set of one element. If called with multiple arguments, an independent set for every element is made.
Source Files