Documentation
¶
Overview ¶
Package unionfind implements union-find data structures and algorithms. It supports union and find queries.
The union-find (a.k.a. disjoint-sets) data type is collection of n elements. Intially, each element belongs to exactly one set (n sets initially). Each set is represented by one element (canonical element, root, identifier, leader, or set representative). The union operation merges the set containing the element p with the set containing the element q. The find operation returns the canonical element of the set containing the element p.
Elements in one set are considered connected to each other. "p is connected to q" is an equivalence relation:
Reflexive: p is connected to p. Symmetric: If p is connected to q, then q is connected to p. Transitive: If p is connected to q and q is connected to r, then p is connected to r.
An equivalence relation partitions the objects into equivalence classes.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type UnionFind ¶
type UnionFind interface {
Union(int, int)
Find(int) (int, bool)
IsConnected(int, int) bool
Count() int
}
UnionFind is the interface a union-find data type.
func NewQuickFind ¶
NewQuickFind creates a new union-find data structure with quick find.
func NewQuickUnion ¶
NewQuickUnion creates a new union-find data structure with quick union.
func NewWeightedQuickUnion ¶
NewWeightedQuickUnion creates a new weighted union-find data structure with quick union.
Source Files