11个版本 (4个重大更新)
| 0.5.4 | 2020年7月24日 |
|---|---|
| 0.5.3 | 2020年7月24日 |
| 0.4.0 | 2020年7月24日 |
| 0.3.1 | 2020年7月24日 |
| 0.1.1 | 2020年7月23日 |
#1191 in 算法
每月58次下载
32KB
305 行
toposort-scc
拓扑排序的Kahn算法和强连通分量的Kosaraju算法的实现。
- 基于邻接表的图数据结构（
IndexGraph） - 一个时间复杂度为O(V + E)和额外空间为O(V)的拓扑排序算法（Kahn算法）
- 一个时间复杂度和额外空间均为O(V)的算法，用于在图中找到强连通分量（Kosaraju算法）
- 这两个算法都可以在
IndexGraph上作为单独的方法（.toposort()和.scc()）或作为一个组合方法（.toposort_or_scc()）提供
id-arena特性增加了一个额外的包装类型（ArenaGraph），它允许对使用id-arena crate构建的任意图结构进行拓扑排序和查找强连通分量，通过创建一个已排序的代理图并返回原始图中的索引列表来实现。
示例
此示例创建了一个来自拓扑排序的维基百科页面的示例图的IndexGraph。
创建了一个包含循环的图的副本，以演示如何查找强连通分量。
use toposort_scc::IndexGraph;
let g = IndexGraph::from_adjacency_list(&vec![
vec![3],
vec![3, 4],
vec![4, 7],
vec![5, 6, 7],
vec![6],
vec![],
vec![],
vec![]
]);
let mut g2 = g.clone();
g2.add_edge(0, 0); // trivial cycle [0]
g2.add_edge(6, 2); // cycle [2, 4, 6]
assert_eq!(g.toposort_or_scc(), Ok(vec![0, 1, 2, 3, 4, 5, 7, 6]));
assert_eq!(g2.toposort_or_scc(), Err(vec![vec![0], vec![4, 2, 6]]));
文档
文档通过rustdoc提供，可以使用cargo doc构建，或在网上查看docs.rs/toposort-scc/。
许可
许可协议为以下之一
- Apache许可证版本2.0（LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0）
- MIT许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）
由您选择。
贡献
除非您明确表示，否则您有意提交以包含在您的工作中的任何贡献（根据Apache-2.0许可证定义），将如上双重许可，不附加任何额外条款或条件。