Crate union_find

source ·
Expand description

An implementation of the Union-Find datastructure.

This crate implements 2 variations of the union find datastructure. QuickFindUf implements an always O(1) find while QuickUnionUf has a union operation that is always O(1).

There is also the option whether the union operation joins the underlying tree structure by size or by rank via the UnionBySize, UnionByRank, UnionByRankSize and UnionBySizeRank structs that need to be passed to the Union Find datastructure.

use union_find::{UnionFind, UnionBySize, QuickUnionUf};

// build a union find datastructure for 10 elements with quick unions,
// merge the unions by size.
let mut uf = QuickUnionUf::<UnionBySize>::new(10);

// initially each element is in it's own set
for i in 0..10 {
    assert_eq!(uf.find(i), i);
}

// join sets containing 0 and 1
assert!(uf.union(0,1));

assert_eq!(uf.find(0), 0);
assert_eq!(uf.find(1), 0);
for i in 2..10 {
    assert_eq!(uf.find(i), i);
}

Structs§

  • QuickFindUf
    Union-Find implementation with quick find operation.
  • QuickUnionUf
    Union-Find implementation with quick union operation.
  • UnionByRank
    Operates the union with using the rank of the sets as weight.
  • UnionByRankSize
    Operates the union with using the rank and the size of the sets as weight.
  • UnionBySize
    Operates the union with using the size of the sets as weight.
  • UnionBySizeRank
    Operates the union with using the size and the rank of the sets as weight.

Enums§

Traits§

  • Union
    The value that can be contained with Union.
  • UnionFind
    APIs for Union-Find operation.