この種のグラフの保存方法は？

Question

双方向エッジを持つグラフがあり、重みはないとします。たくさんのメモリを無駄にしないように、どのように保存すればいいですか？高速化し、すべての頂点の隣人に素早くアクセスできますか？私が意味する、今までこのようなSTHのために：{(1,2)(1,5)(1,3)(2,4)(2,3)}私は、配列を使用している：array[1][2]=1は1と2の間の接続があることを意味しているとの二つの問題があります。

• a）はグラフのように双方向、(1,2)は(2,1)が存在することを意味します。私は、後2者の隣人への容易なアクセスを持っているしたい場合は、私は、反復ごとに2つの変更を加える必要があります：私はいくつかの頂点を知っているとき）array[1][2]=1、array[2][1]=1

• Bを（たとえば5）私が検索する必要があり、唯一の隣人が残っています全体array[5][x]は万人の頂点のグラフのためにあらゆる可能なx

• c）をチェックして、このモンスターがどんな競技で使用するにはあまりにも膨大になり

あなたは私を助けて、私指してもらえ私の問題に対する解決策？

Answer 1

あなたがセットのマップを望むように見えます。

std::map< int, std::set<int> >

だから、int型のためにあなたは、セット内のすべての隣国のコレクションを格納することができます。このコレクションを操作する関数が必要になります。

ノードの数がカウント可能な場合、つまり0からNの範囲にあり、これらの数字がすべて含まれている場合は、std::vector< std::set<int> >を使用すると効率的です。たとえば、ノード数が20,000の場合は、std::vector< std::bitset<N> >またはstd::vector<boost::dynamic_bitset> >を使用することもできます。したがって、それぞれが50MBのメモリ（約）の2500バイト（さらにオーバーヘッドのビット）の20,000ビットセットを割り当てることができます。

これはあなたが持っているモデルに比べてはるかにコンパクトなモデルですが、多くはありません。百万の頂点を持っている場合は約125GBですので、このモデルを使用することはできませんが、セットを使用する必要があります。また、頂点を通して反復することで、その近傍が何であるかを見ることができます。

しかし、隣接していない頂点がたくさんあり、それらに順番に番号が付けられていない限り、マップオーバーベクトルの利点はありません。

「トン」と呼ばれるメモリの量がわかりません。私が外に出したモデルは定数メモリを使っていますが、セットのマップはあなたが持っている近隣関係の数に比例したメモリを使いますが、いっぱいになるとビットセットのベクトルよりはるかにコンパクトになりますので、

Answer 2

三角行列を使用できます。つまり、x< yならば（x、y）は存在しますが、（y、x）は存在しません。そして、（x、y）に対応する値があります。

http://www.codeguru.com/cpp/cpp/algorithms/general/article.php/c11211およびhttps://stackoverflow.com/questions/8305186/isolating-triangle-array-items-and-evaluating-them-for-equality-then-outputtingを参照してください。