对于大型图形合适的数据结构 [英] 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++.

我已经看到了previous帖子......但我就Dijkstra算法寻找一个合适的数据结构。

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

大我的意思是包含100多万个节点和边的图。

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

推荐答案

这是常见的重新present邻接表为整数，其中整数是一个节点的索引列表。如何有关而不是把邻接表作为一个位串得到一些更多的空间效率 00010111000 ... 凡 1 在第n个位置重新presents这个节点与节点之间的边缘 N ？那么COM preSS一些标准算法的比特串; uncom preSS它，你需要它。该位串将可能COM preSS pretty好，所以这个交易对更高计算成本空间效率。

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屋！