适用于大图形的数据结构 [英] Suitable data structure for large graphs

问题描述

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

I have a large graph, is there any other data structure other than adjacency list and "adjacency matrix" in c++ stl or some other data structure which I can employ for such a large graph, actually the adjacency matrix of my graph does not fit in the main memory. My graph is directed and I am implementing dijkstra algorithm in C++.

我看过以前的帖子...但我正在寻找一个合适的数据结构dijkstra 。

I have seen the previous posts...but I am searching for a suitable data structure with respect to dijkstra.

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

By large I mean a graph containing more than 100 million nodes and edges.

推荐答案

通常将邻接列表表示为整数列表，其中整数是节点的索引。通过将邻接列表视为位串 00010111000 ... 来获得一些更多的空间效率，其中 1 在第n个位置表示此节点和节点 n 之间的边缘？然后通过一些标准算法压缩位串;解压缩它，因为你需要它。位串可能压缩得相当好，所以这种方法可以提高空间效率，从而提高计算成本。

It's common to represent adjacency lists as lists of integers, where the integer is the index of a node. How about getting some more space efficiency by instead treating the adjacency list as a bit string 00010111000... where a 1 in nth position represents an edge between this node and node n? Then compress the bitstring by some standard algorithm; uncompress it as you need it. The bit strings will probably compress pretty well, so this trades space efficiency for higher computational cost.

这篇关于适用于大图形的数据结构的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！