就内存空间或构建时间而言，有谁知道保留图形信息的更有效方法（即比将其保留为二维数组更有效）？
您可以假设它的值限制在 0-255 之间。
谢谢！
问问题
5946 次
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 回答