pub fn girth<T>(graph: &Graph<T, impl Clone>) -> usizeExpand description
计算图的 girth(最短环的长度)
Girth 是图中最短环的长度。如果图中没有环,返回 0。
§复杂度
- 时间:O(V * (V + E)) - 对每个节点进行 BFS
- 空间:O(V)
§示例
use god_gragh::prelude::*;
use god_gragh::algorithms::properties::girth;
let graph = GraphBuilder::directed()
.with_nodes(vec!["A", "B", "C"])
.with_edges(vec![(0, 1, 1.0), (1, 2, 1.0), (2, 0, 1.0)])
.build()
.unwrap();
let g = girth(&graph);
assert_eq!(g, 3); // 三角形环