disjoint

此crate提供了在100%安全Rust中的快速不交集数据结构实现。

DisjointSet 是一个非常轻量级的不交集数据结构，没有附加到集合元素上的额外数据。如果您自己管理与元素相关的数据，并只想跟踪哪些元素被连接，请使用此数据结构。

DisjointSetVec<T> 将 DisjointSet 与 Vec<T> 结合，因此它管理连续的数据条目 T 并跟踪哪些条目被连接。如果您希望不交集数据结构为每个元素包含一些额外的数据 T，请使用此数据结构。

示例

不交集数据结构可以应用于寻找无向边权图的最小生成树。让我们假设我们使用以下图形接口

    trait Edge : Copy {
        fn first_vertex(&self) -> usize;
        fn second_vertex(&self) -> usize;
    }
    
    trait Graph {
        type E : Edge;
        fn edges_ordered_by_weight(&self) -> Vec<Self::E>;
        fn number_vertices(&self) -> usize;
        fn new(edges: Vec<Self::E>) -> Self;
    }

然后使用提供的 DisjointSet 结构及其方法 is_joined 和 join 来实现克鲁斯卡尔算法以找到最小生成树。

use disjoint::DisjointSet;

fn minimum_spanning_forest<G : Graph>(graph: &G) -> G {
    let mut result_edges = Vec::new();
    let mut vertices = DisjointSet::new(graph.number_vertices());

    for edge in graph.edges_ordered_by_weight() {
        if !vertices.is_joined(edge.first_vertex(), edge.second_vertex()) {
            vertices.join(edge.first_vertex(), edge.second_vertex());
            result_edges.push(edge);
        }
    }
    
    Graph::new(result_edges)
}

我们甚至可以使用 join 返回 true 的事实（如果元素尚未连接），以进一步简化算法（这种变化有时称为快速并查集）

use disjoint::DisjointSet;

fn minimum_spanning_forest_quick_find<G : Graph>(graph: &G) -> G {
    let mut result_edges = Vec::new();
    let mut vertices = DisjointSet::new(graph.number_vertices());

    for edge in graph.edges_ordered_by_weight() {
        if vertices.join(edge.first_vertex(), edge.second_vertex()) {
            result_edges.push(edge);
        }
    }
    
    Graph::new(result_edges)
}

有关如何使用此crate的更多详细信息，请参阅文档。

变更日志

此crate维护一个变更日志。

许可

以下任一许可下授权：

• Apache License, Version 2.0, (LICENSE-APACHE 或 https://www.apache.org/licenses/LICENSE-2.0)
• 麻省理工学院许可证（LICENSE-MIT 或 https://opensource.org/licenses/MIT）

由您选择。

贡献

除非您明确声明，否则根据 Apache-2.0 许可证定义的，您有意提交并包含在作品中的任何贡献，将双重许可，如上所述，无任何额外条款或条件。