c++ - 适合大图的数据结构

Question

我有一个大图，除了 c++ stl 中的邻接列表和“邻接矩阵”或我可以用于这么大的图的其他数据结构之外，是否还有其他数据结构，实际上我的图的邻接矩阵不适合主内存。我的图是有向的，我正在用 C++ 实现 dijkstra 算法。

我已经看过之前的帖子......但我正在寻找一个合适的关于 dijkstra 的数据结构。

大我的意思是一个包含超过 1 亿个节点和边的图。

Answer 1

通常将邻接列表表示为整数列表，其中整数是节点的索引。00010111000...通过将邻接表视为位串，其中1第 n 个位置的 a 表示该节点和节点之间的一条边，如何获得更多的空间效率n？然后通过一些标准算法压缩位串；根据需要解压缩它。位串可能会很好地压缩，因此这会以空间效率换取更高的计算成本。