Skip to main content

girth

Function girth 

Source
pub fn girth<T>(graph: &Graph<T, impl Clone>) -> usize
Expand 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); // 三角形环