1

就内存空间或构建时间而言,有谁知道保留图形信息的更有效方法(即比将其保留为二维数组更有效)?

您可以假设它的值限制在 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 为行数),除非您有一个非常密集的图。如果您只有一个简单的未加权图,则可以使用位数组来节省一些内存。

边列表很简单,但比邻接矩阵慢,并且如果您有一个稀疏图(2*M,其中 M 是边数),则内存效率很高。

邻接列表稍微复杂一些(因为您需要可变大小的数组),但如果您有大量边(2*N+M,其中 N 是顶点数,M 是边缘)

邻接矩阵占用 (N N b) 个空间。边缘列表占用 ((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 格式将顶点和边存储在单独的数组中,这些数组的索引分别对应于顶点或边的标识符。边数组按每条边的来源排序,但只包含边的目标。顶点数组将偏移量存储到边数组中,提供从每个顶点传出的第一条边的偏移量。通过访问 edge_array[vertex_array[i]], edge_array[vertex_array[i]+1], ..., edge_array[vertex_array[i+1]] 来迭代图中第 i 个顶点的出边。这种格式将内存使用减少到 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 回答