graph_spanning/lib.rs
1//! # graph-spanning
2//!
3//! Minimum spanning tree and connectivity algorithms built on [`graph_core`]'s
4//! [`Graph`] trait.
5//!
6//! ## Algorithms
7//!
8//! | Module | Algorithm | Complexity |
9//! |----------------------|-----------------------------------------|----------------|
10//! | [`mod@disjoint_set`] | Union-Find with path compression | O(α(n)) |
11//! | [`mod@kruskal`] | Kruskal's MST | O(E log E) |
12//! | [`mod@prim`] | Prim's MST | O((V+E) log V) |
13//! | [`mod@bridges`] | Tarjan's bridge finding | O(V+E) |
14//! | [`mod@articulation`] | Articulation points (cut vertices) | O(V+E) |
15//!
16//! [`Graph`]: graph_core::Graph
17
18/// Articulation points (cut vertices) via DFS disc/low-link values.
19pub mod articulation;
20/// Bridge finding (cut edges) via Tarjan's DFS disc/low-link algorithm.
21pub mod bridges;
22/// Union-Find with union-by-rank and path compression.
23pub mod disjoint_set;
24/// Kruskal's minimum spanning tree: sort edges, union-find cycle check.
25pub mod kruskal;
26/// Prim's minimum spanning tree: priority-queue edge relaxation.
27pub mod prim;
28
29pub use articulation::articulation_points;
30pub use bridges::bridges;
31pub use disjoint_set::DisjointSet;
32pub use kruskal::{kruskal, SpanningTree};
33pub use prim::prim;