我正在处理一个非常大的图形，其中节点数量达到5亿个，节点的平均度数为100。因此，这是一种稀疏图。我还必须存储每条边的权重。我目前正在使用两个向量来实现，如下所示：
// V could be 100 million
vector<int> *AdjList = new vector<int>[V];
vector<int> *Weight = new vector<int>[V];
使用vector嵌套vector似乎不太节省空间。 它需要超过400GB的存储空间。 有没有更好的节省空间的方法来在内存中存储这个大图？ 有使用任何C ++库的建议吗？
初步说明
您可以考虑使用向量的向量来代替动态内存分配：
vector<vector<int>> AdjList(V);
vector<int>。每个向量都需要一些空间开销来管理其项目的大小和位置。不幸的是，通过在不同的向量/数组中保留权重，您会使这种开销加倍（以及与添加新链接相关的隐藏内存管理）。那么为什么不重新组合邻接表和权重呢？struct Link {
int target; // node number that was in adj list. Hope none is negative!!
int weight;
};
vector<vector<Link>> AdjList(V);
这个结构是稀疏的吗？
如果大多数节点都有某种链接，那就很好。
如果相反，许多节点没有出站链接（或者您有大量未使用的节点ID范围），则可以考虑：
map<int, vector<Link>> AdjList;
map 是一种关联数组。只有具有出链的节点才会有向量。顺便说一句，您可以使用任何编号方案，甚至负数。
您甚至可以更进一步，使用双重映射。第一个映射给出了出链的节点。第二个映射将目标节点映射到其权重：
map<int, map<int, int>> Oulala;
map和vector动态管理内存。但是如果您有很多预定大小的小对象，则可以考虑使用自己的分配器。这可以显着优化内存管理开销。还有其他一些图形库可用，但许多库似乎已不再维护或者没有设计用于大容量。
X，表示变量的索引，如果函数F(..X=true..)为真，则继续在节点的高枝上到达叶节点true，如果F(..X=false..)为真，则继续在低枝上到达表示真的叶节点。这被称为布尔函数的Shannon扩展（使用相同的扩展公式也是计算布尔函数的硬件设计的一种方式，使用多路复用器）。true叶子的唯一分支，每个节点都根据输入变量Xi进行分支（根据Xi的true或false值在低或高方向上分支）。同一图表可用于保留多个函数（每个节点是不同的函数）。有成千上万的文章介绍BDD及其衍生品（例如通过改变每个节点调度的解释，我们得到ZDD，用于无序集合的紧凑表示）。关于这个主题的典型文章是C. Dong P. Molitor的What graphs can be efficiently represented by BDDs?。
当您了解BDD的基础知识后，如果您有耐心观看更长的演示，则this video非常好，并总结了如何将图形编码为BDD。
当需要管理数百万个节点时，BDD是现代专业软件的做法。
如果图形不会被修改，考虑使用两个向量：
struct edge { int target; int weight; };
std::vector<edge> edges;
std::vector<int> nodes; // begin-index into edges
这应该可以最小化开销。
当然，如果您无法进一步减少图形，则如此。
V向量的数组。老实说，看一下一些 C++ 图库，并确保你知道 C++ 语言本身的基础知识。 - Ulrich EckhardtV，因为向量的数量也将是V。但程序需要找出每个节点有多少相邻节点。因此，我创建了V个向量，然后在程序内部开始向每个向量添加相邻节点。 - viz12