fera-unionfind

并查集（非交集数据结构）。

该crate是fera项目的一部分。

许可证

根据Mozilla公共许可证2.0许可。贡献将接受相同的许可证。

lib.rs:

并查集（非交集数据结构）实现。

该实现使用路径压缩和秩启发式算法。使用默认类型参数时，父节点和秩存储在std::collections::HashMap中。如果键在范围0..n内，则使用UnionFindRange。

键应该实现Copy。如果键没有实现Copy，应使用存储在其他地方的键的引用。

可以通过fera crate使用该crate。

示例

use fera_unionfind::UnionFind;

// Explicit type to make it clear
let mut s: UnionFind<&'static str> = UnionFind::new();

s.make_set("red");
s.make_set("green");
s.make_set("blue");

assert_eq!(3, s.num_sets());
assert!(!s.in_same_set("red", "green"));
assert!(!s.in_same_set("red", "blue"));

s.union("red", "blue");

assert_eq!(2, s.num_sets());
assert!(!s.in_same_set("red", "green"));
assert!(s.in_same_set("red", "blue"));

使用非Copy键。

use fera_unionfind::UnionFind;

// This is invalid. String does not implement copy.
// let mut x: UnionFind<String> = UnionFind::new();
// Lets store the keys in a vector and use references (references are Copy).
let v = vec!["red".to_string(), "green".to_string(), "blue".to_string()];

// The type of s is Union<&'a String> where 'a is the lifetime of v.
let mut s = UnionFind::new();

s.make_set(&v[0]);
s.make_set(&v[1]);
s.make_set(&v[2]);

assert_eq!(3, s.num_sets());
assert!(!s.in_same_set(&v[0], &v[1]));
assert!(!s.in_same_set(&v[0], &v[2]));

s.union(&v[0], &v[2]);

assert_eq!(2, s.num_sets());
assert!(!s.in_same_set(&v[0], &v[1]));
assert!(s.in_same_set(&v[0], &v[2]));

使用范围0..n内的键。

use fera_unionfind::UnionFindRange;

let mut s = UnionFindRange::with_keys_in_range(..5);

// It is not necessary to call UnionFind::make_set

assert_eq!(5, s.num_sets());
assert!(!s.in_same_set(0, 1));
assert!(!s.in_same_set(0, 2));

s.union(0, 2);

assert_eq!(4, s.num_sets());
assert!(!s.in_same_set(0, 1));
assert!(s.in_same_set(0, 2));

s.reset();
assert_eq!(5, s.num_sets());