2个不稳定版本
| 0.2.0 | 2023年1月10日 |
|---|---|
| 0.1.0 | 2022年12月6日 |
#481 in 嵌入式开发
50KB
846 行
为裸机环境提供的无分配union-find库
该库提供了以下与 UnionFind 一起使用的算法。
- QuickFind
- QuickUnion
- 加权QuickUnion
- 带路径压缩的加权QuickUnion（默认）
设置
Cargo.toml 设置
[dependencies]
pulau-rs = "0.2.0"
渐近复杂度
| 算法 | 结构体 | 初始化 | 合并 | 查找 | 连接 |
|---|---|---|---|---|---|
| QuickFind | QuickFind |
O(N) |
O(N) |
O(1) |
O(1) |
| QuickUnion | QuickUnion<false, false> |
O(N) |
O(N) |
O(N) |
O(N) |
| 加权QuickUnion | QuickUnion<ByRank, false> |
O(N) |
O(lg N) |
O(lg N) |
O(lg N) |
| 带路径压缩的加权（Rank）QuickUnion | QuickUnion<ByRank, true> |
O(N) |
Θ(α(N)) |
Θ(α(N)) |
Θ(α(N)) |
| 带路径压缩的加权（Size）QuickUnion | QuickUnion<BySize, true> |
O(N) |
Θ(α(N)) |
Θ(α(N)) |
Θ(α(N)) |
*其中 α 是逆 Ackermann 函数
UnionFind的应用
- 检查图中的连通分量
- 检查图中的环
- 在图像中搜索连通分量
- 使用Kruskal找到最小生成树
示例用法
use pulau_rs::{UnionFind, QuickFind, QuickUnion, BySize};
fn make_uf_quickfind() {
// construct with quickfind algorithm with fixed size 10
let mut uf = UnionFind::<QuickFind, u32, 10, 0>::new();
}
fn make_uf_quickunion() {
// construct weighted quickunion with path compression algorithm with fixed size 10
let mut uf = UnionFind::<QuickUnion, u32, 10>::new();
// construct weighted quickunion with path compression using size heuristics and fixed size 10
let mut uf_with_sz = UnionFind::<QuickUnion<BySize>, u8, 10>::new();
uf.union_sets(1,2);
uf.union_sets(2,3);
uf.union_sets(2,3);
assert!(uf.connected(1, 3));
}
许可证
pulau-rs 在MIT许可证下授权（LICENSE-MIT 或 http://opensource.org/licenses/MIT）