disjoint-hash-set

一个用于通过其哈希值识别的连接组件增量跟踪的并查集/集合合并的Rust实现。

集成了基于排名的集合合并和路径压缩，以确保与并查集算法相关的渐近最优时间复杂度。

use disjoint_hash_set::DisjointHashSet;

let mut djhs = DisjointHashSet::new();
djhs.link("hello", "hi");
djhs.link("hello", "👋");
assert!(djhs.is_linked("hi", "👋"));

// `DisjointHashSet` can be built from an iterator of edges
let djhs = vec![("a", "b"), ("a", "c"), ("d", "e"), ("f", "f")]
    .into_iter()
    .collect::<DisjointHashSet<_>>();

// Consume djhs to iterate over each disjoint set
let sets = djhs.sets(); // looks like [{"a", "b", "c"}, {"d", "e"}, {"f"}]
assert_eq!(sets.count(), 3);

lib.rs:

适用于通过其哈希值识别的连接组件增量跟踪的并查集/集合合并数据结构。

组件的总数无需事先知道。组件之间的连接以及组件本身可以在发现时添加。

采用基于排名的集合合并和路径压缩，导致与并查集算法相关的渐近最优时间复杂度。

示例

use disjoint_hash_set::DisjointHashSet;

let mut djhs = DisjointHashSet::new();
djhs.link("hello", "hi");
djhs.link("hello", "👋");
assert!(djhs.is_linked("hi", "👋"));

// `DisjointHashSet` can be built from an iterator of edges
let djhs = vec![("a", "b"), ("a", "c"), ("d", "e"), ("f", "f")]
    .into_iter()
    .collect::<DisjointHashSet<_>>();

// Consume djhs to iterate over each disjoint set
let sets = djhs.sets(); // looks like [{"a", "b", "c"}, {"d", "e"}, {"f"}]
assert_eq!(sets.count(), 3);