1

メモリスペースまたはビルド時間の観点から、グラフ情報を保持するためのより効率的な方法（つまり、2次元配列として保持するよりも効率的）を知っている人はいますか？

値は0〜255の間に制限されていると想定できます。

ありがとう！

4

4 に答える 4

3

(有向) グラフを表すいくつかの標準的な方法を次に示します。

4 つのノードのグラフの場合:

隣接行列:

  0  1  2  3 
0 F  F  T  F
1 T  F  T  T
2 T  F  F  F
3 F  F  F  F

エッジ リスト:

((0, 2), (1, 0), (1, 2), (1, 3), (2, 0))

隣接リスト:

(
 (0, (2,)     ), 
 (1, (0, 2, 3)), 
 (2, (0,)     ),
 (4, (,)      ),
)

隣接行列は単純で最も高速な表現ですが、グラフが非常に密集している場合を除き、最も多くのメモリ (N*N、N は行数) を消費します。単純な重み付けされていないグラフしかない場合は、ビット配列を使用してメモリを節約できる場合があります。

Edge List はシンプルですが、Adjacency Matrix よりも遅く、スパース グラフ (2*M、M はエッジの数) の場合はメモリ効率が高くなります。

隣接リストは少し複雑ですが (可変サイズの配列が必要なため)、多数のエッジ (2*N+M、N は頂点の数、M は頂点の数) がある場合は、エッジ リストよりもメモリ効率が高くなります。エッジ)

隣接行列は (N N b) スペースを取ります。Edge List は ((2+b)*N) メモリを必要とします。また、隣接リストには (2*N+M*(1+b)) メモリが必要です。

頂点が常に 256 (8 ビット) 未満であり、重みが 256 (8 ビット) 未満であることがわかっている場合、隣接行列は (N*N*8) のスペースを占有します。エッジ リストは (24*N) メモリを必要とします。また、隣接リストには (16*N+M*16) のメモリが必要です。

于 2010-10-10T21:22:14.867 に答える
2

作成後にグラフを変更する必要がない場合は、圧縮スパース行（CSR）形式を確認してください。BGLからの説明：

CSR形式では、頂点とエッジが別々の配列に格納され、これらの配列へのインデックスは、それぞれ頂点またはエッジの識別子に対応します。エッジ配列は各エッジのソースでソートされますが、エッジのターゲットのみが含まれます。頂点配列はオフセットをエッジ配列に格納し、各頂点から出力される最初のエッジのオフセットを提供します。グラフのi番目の頂点のアウトエッジでの反復は、edge_array [vertex_array [i]]、edge_array [vertex_array [i] +1]、...、edge_array [vertex_array [i+1]]にアクセスすることで実現されます。この形式は、メモリ使用量をO（n + m）に最小化します。ここで、nとmは、それぞれ頂点とエッジの数です。nとmを掛けた定数は、エッジ配列と頂点配列へのインデックスを表すために必要な整数のサイズに基づいています。

これがオフセット配列の良い説明です：

       Offset              Neighbours
   1      1    -------------->  2
   2      3    ------------     3
   3      5    ----------  |->  1
   4      9    --------  |      3
   5     10    ------  | |--->  1
   6     12    ----  | |        2
   7     14    --  | | |        4
                 | | | |        6
                 | | |  ----->  3
                 | |  ------->  6
                 | |            7
                 |  --------->  5
                 |              7
                  ----------->  5
                                6

エッジの効率的な挿入

作成後にエッジを挿入できるようにすることは、基本的にNeighbours配列を「リンクリスト」にすることで実現できます。オフセットは最初のネイバーを指し、各ネイバーにはNextフィールドが含まれています。これは次のエッジを指します。

同じソースから：

        Offset                 Node  Next
   1      1    -------------->  2    2
   2      3    ------------     3   -1
   3      5    ----------  |->  1    4
   4      9    --------  |      3   -1
   5     10    ------  | |--->  1    6
   6     12    ----  | |        2    7
   7     14    --  | | |        4    8
                 | | | |        6    9
                 | | |  ----->  3   -1
                 | |  ------->  6   11
                 | |            7   -1
                 |  --------->  5   13
                 |              7   -1
                  ----------->  5   15
                                6   -1
于 2010-10-10T23:34:30.623 に答える
1

グラフがかなりまばらな場合は、隣接行列ではなくエッジ リスト (ノードからノードへ) として保存することで、スペースを節約できます。もちろん、すべてのエッジが双方向の場合は、エッジを一度だけ保存する必要があります。

于 2010-10-10T21:06:44.097 に答える
0

ここで役立つとわかったグラフ表現のリストがあります。

グラフのデータ構造

于 2010-10-11T07:08:40.597 に答える