我有一个大图，除了 C++ STL 中的邻接表和“邻接矩阵”或其他一些我可以用于如此大图的数据结构之外，是否还有其他数据结构，实际上我图的邻接矩阵确实如此不适合主存储器。我的图是有向图，我正在用 C++ 实现 dijkstra 算法。
我看过以前的帖子...但我正在寻找适合 dijkstra 的数据结构。
我指的是包含超过 1 亿个节点和边的图。
最佳答案
通常将邻接表表示为整数列表，其中整数是节点的索引。如何通过将邻接列表视为位串 00010111000... 来提高空间效率，其中第 n 个位置的 1 表示此节点和节点 n？然后通过一些标准算法压缩位串；根据需要解压缩它。位串可能会压缩得很好，因此这会以空间效率换取更高的计算成本。
关于c++ - 适用于大图的数据结构，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/10799659/