Graph 模块详解

Graph 模块提供随机图/树生成功能、带权图生成、Erdos–Rényi 模型，以及若干基础图算法（BFS、连通分量）。

主要生成函数

• random_tree(int n, int seed = 0)：生成 n 个节点的随机树（返回边列表，节点编号 1..n）。
• random_graph(int n, int m, bool directed = false, int seed = 0)：生成 m 条边的随机无向/有向图（无权）。
• random_weighted_graph(int n, int m, double minw, double maxw, int seed = 0)：在 random_graph 基础上为每条边随机赋权。
• erdos_renyi(int n, double p, int seed = 0)：Erdos–Rényi G(n, p) 模型；对每一对 (u,v) 以概率 p 添加边。

实用函数

• to_edge_list_string(const std::vector<std::pair<int,int>>& edges)：导出为文本边列表，便于写文件或打印。
• bfs(int n, const std::vector<std::pair<int,int>>& edges, int start=1)：返回 BFS 的访问顺序（假设 1..n 节点）。
• connected_components(int n, const std::vector<std::pair<int,int>>& edges)：返回 {component_count, assignment_vector}，assignment_vector[i] 表示节点 i 所属组件编号。

示例

using namespace STAR_CPP;
// 生成随机树
auto tree_edges = Graph::random_tree(10, 42);
std::cout << Graph::to_edge_list_string(tree_edges);

// 生成带权图
auto wedges = Graph::random_weighted_graph(20, 30, 0.1, 10.0, 99);
for (auto &t: wedges) std::cout << std::get<0>(t) << " " << std::get<1>(t) << " " << std::get<2>(t) << "\n";

// Erdos-Renyi
auto er = Graph::erdos_renyi(50, 0.05, 10);
std::cout << "edges: " << er.size() << '\n';

// BFS / 连通分量
auto order = Graph::bfs(50, er, 1);
auto cc = Graph::connected_components(50, er);
std::cout << "components: " << cc.first << '\n';

扩展建议

• 若需要最短路/最小生成树等算法，我可以继续添加 Dijkstra、Kruskal/Prim 等实现并提供使用示例。
• 若需要输出为 GraphViz dot 格式或 GraphML，也可以添加序列化函数以便可视化。