1

亲爱的，这一切都很容易，我希望！

我有一个图表，我想静态分配它。我知道我会有N节点，并且每个节点最多有 K << N边（例如，N = 1,000,000和K = 3）。如果我不仅可以初始化具有一定数量节点的图，而且还可以初始化具有预定义数量的边，那将很方便。

你知道这是否可能吗？

如果不是，您是否建议放弃邻接矩阵的邻接列表？我将拥有大量的边，这就是为什么静态分配会很棒。

干杯!

4

2 回答 2

2

Boost.Graph 有Compressed Sparse Row Graph，它做的事情接近你想要的。它对内存非常友好。与其他 Boost 图一样，您可以将其声明为有向、无向等，并将属性与其元素相关联。

需要注意的是，此图是不可变的，这意味着您可以创建和填充它，但以后不能更新。生成图形时，您需要准备好所有边。在此处查看类似的 SO 主题

于 2013-11-08T22:24:22.633 回答
0

我没有测试它，但考虑到这enum { A, B, C, D, E, F, N };意味着A = 0, B = 1, ..., N = 6，Graph g(N);似乎在编译时为N = 6节点和N*N边缘分配内存。除非使用无向图，否则似乎不可能减少或限制边的数量。

来源： http: //www.boost.org/doc/libs/1_54_0/libs/graph/doc/adjacency_matrix.html

于 2013-11-08T11:40:24.413 回答