Expand description
连通性问题
§UF 使用
use algorithms_fourth::graph::connect::UF;
let mut uf = UF::new(8);
assert_eq!(uf.count(),8);
uf.union(0, 1);
assert_eq!(uf.count(),7);
uf.union(2,3);
assert_eq!(uf.count(),6);
uf.union(4, 5);
assert_eq!(uf.count(),5);
uf.union(6, 7);
assert_eq!(uf.count(),4);
assert!(uf.connected(0, 1));
assert!(!uf.connected(2, 1));
uf.union(0, 2);
uf.union(4,6);
uf.union(0, 4);
assert_eq!(uf.count(),1);§Connect 使用
use algorithms_fourth::{
add_edge,
graph::{connect::Connect, Graph},
};
let mut g = Graph::new(13);
add_edge!(g, 0, 6, 5, 2, 1);
g.add_edge(1, 0);
g.add_edge(2, 0);
add_edge!(g, 3, 5, 4);
add_edge!(g, 4, 5, 6, 3);
add_edge!(g, 5, 3, 4, 0);
add_edge!(g, 6, 0, 4);
add_edge!(g, 7, 8);
add_edge!(g, 8, 7);
add_edge!(g, 9, 11, 10, 12);
add_edge!(g, 10, 9);
add_edge!(g, 11, 9, 12);
add_edge!(g, 12, 11, 9);
// g.print_dot("graph.dot");
let connect = Connect::new(&g);
// connect.print_dot("connect.dot");
assert_eq!(connect.count(), 3);
assert_eq!(connect.connected(8, 7), true);
assert_eq!(connect.connected(9, 10), true);
assert_eq!(connect.connected(0, 6), true);
assert_eq!(connect.connected(0, 8), false);
assert_eq!(connect.connected(10, 12), true);
assert_eq!(connect.id(6), 0);
assert_eq!(connect.id(8), 1);
assert_eq!(connect.id(12), 2);