就内存空间或构建时间而言,有谁知道保留图形信息的更有效方法(即比将其保留为二维数组更有效)?
您可以假设它的值限制在 0-255 之间。
谢谢!
就内存空间或构建时间而言,有谁知道保留图形信息的更有效方法(即比将其保留为二维数组更有效)?
您可以假设它的值限制在 0-255 之间。
谢谢!
以下是表示(有向)图的一些标准方法:
对于 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) 内存。
如果您在创建后不需要修改图形,请查看压缩稀疏行 (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
如果图形相当稀疏,那么您将通过将其存储为边列表(从节点到节点)而不是邻接矩阵来节省空间。如果所有边都是双向的,那么您当然只需要存储任何边一次。
这里有一个我发现有用的图形表示列表: