god_graph/generators/
tree.rs

1//! 树生成器
2
3use crate::graph::builders::GraphBuilder;
4use crate::graph::Graph;
5
6/// 生成随机树
7///
8/// 使用 Prüfer 序列方法生成均匀分布的随机树
9///
10/// # 参数
11/// * `n` - 节点数量
12///
13/// # 返回
14/// 生成的树
15pub fn tree_graph<T>(n: usize) -> Graph<T, f64>
16where
17    T: Clone + Default,
18{
19    if n == 0 {
20        return Graph::undirected();
21    }
22
23    let mut builder = GraphBuilder::undirected().with_nodes((0..n).map(|_| T::default()));
24
25    // 简单实现：生成一条路径
26    for i in 0..n - 1 {
27        builder = builder.with_edge(i, i + 1, 1.0);
28    }
29
30    builder.build().unwrap_or_else(|_| Graph::undirected())
31}
32
33/// 生成完全二叉树
34pub fn binary_tree_graph<T>(height: usize) -> Graph<T, f64>
35where
36    T: Clone + Default,
37{
38    let n = (1 << height) - 1; // 2^h - 1
39    let mut builder = GraphBuilder::undirected().with_nodes((0..n).map(|_| T::default()));
40
41    for i in 0..n {
42        let left = 2 * i + 1;
43        let right = 2 * i + 2;
44
45        if left < n {
46            builder = builder.with_edge(i, left, 1.0);
47        }
48        if right < n {
49            builder = builder.with_edge(i, right, 1.0);
50        }
51    }
52
53    builder.build().unwrap_or_else(|_| Graph::undirected())
54}
god_graph/generators/tree.rs

god_graph/generators/
tree.rs
