适用于大图的数据结构

我有一个大图，除了邻接列表和c ++ stl中的“邻接矩阵”之外还有其他任何数据结构，或者我可以用于这样一个大图的其他数据结构，实际上我的图的邻接矩阵不适合主要记忆。 我的图是有针对性的，我正在用C ++实现dijkstra算法。

我已经看过以前的post……但我正在寻找一个适合dijkstra的数据结构。

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

Answer 1

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