c++ - 大きなグラフに適したデータ構造

Question

私は大きなグラフを持っています.c ++ stlの隣接リストと「隣接行列」以外の他のデータ構造、またはそのような大きなグラフに使用できる他のデータ構造はありますか?実際に私のグラフの隣接行列は収まりませんメインメモリ。私のグラフは有向で、ダイクストラ アルゴリズムを C++ で実装しています。

以前の投稿を見たことがあります...しかし、ダイクストラに関して適切なデータ構造を探しています。

概して、1 億を超えるノードとエッジを含むグラフを意味します。

Answer 1

隣接リストを整数のリストとして表すのが一般的です。整数はノードのインデックスです。00010111000...代わりに、隣接リストをビット文字列として扱い、n 番目の位置にある a1がこのノードとノードの間のエッジを表すことで、スペース効率を高めてみnませんか? 次に、標準アルゴリズムによってビット文字列を圧縮します。必要に応じて解凍してください。ビット文字列はおそらくかなりうまく圧縮されるため、これはスペース効率と引き換えに計算コストが高くなります。