当前位置：文江博客话题详情

保存图形的有效方法（二维数组）

发布于 2024-09-26 20:45:47 字数 95 浏览 2 评论 0原文

有谁知道在内存空间或构建时间方面更有效的方法来保存图形信息（即比将其保存为二维数组更有效）？

您可以假设它的值限制在 0-255 之间。

谢谢！

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

戴着白色围巾的女孩 2024-10-03 20:45:47

以下是表示（有向）图的一些标准方法：

对于 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 是顶点数，M 是顶点数），则比边列表更节省内存。边）

邻接矩阵占用 (NNb) 空间。边缘列表占用 ((2+b)*N) 内存。邻接表占用 (2*N+M*(1+b)) 内存。

如果您知道顶点始终少于 256 个（8 位），并且权重小于 256 个（8 位），则邻接矩阵占用 (N*N*8) 空间。边缘列表占用 (24*N) 内存。邻接表占用(16*N+M*16)内存。

Here are a few standard ways to represent a (directed) graph:

For a graph of 4 nodes:

Adjacency matrix:

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

Edge List:

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

Adjacency list:

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

The Adjacency matrix is simple and the fastest representation, but takes the most memory (N*N, where N the number of rows), except if you have an extremely dense graph. You may be able to save some memory by using bit-arrays, if you only have a simple unweighted graph.

Edge List is simple, but slower than Adjacency Matrix, and is memory efficient if you have a sparse graph (2*M, where M is the number of edges).

Adjacency list is slightly more complicated (as you need variable-size array), but more memory efficient than Edge List if you have a large number of edges (2*N+M, where N is the number of vertices, M the number of edges)

The Adjacency Matrix takes (NNb) space. Edge List takes ((2+b)*N) memory. And adjacency list takes (2*N+M*(1+b)) memory.

If you know you always have less than 256 vertices (8-bit), and the weights are less than 256 (8-bit), then the Adjacency Matrix takes (N*N*8) space. Edge List takes (24*N) memory. And adjacency list takes (16*N+M*16) memory.

回复收藏 0 原文

我不是你的备胎 2024-10-03 20:45:47

如果您不需要在创建后修改图形，请查看压缩稀疏行 (CSR) 格式。来自 BGL 的描述：

CSR 格式存储顶点和
单独数组中的边，其中
这些数组的索引
对应于标识符
分别是顶点或边。这
边数组按来源排序
每条边，但仅包含
边缘的目标。顶点
数组将偏移量存储到边缘
数组，提供的偏移量
从每个顶点传出的第一条边。
迭代出边
图中的第 i 个顶点是通过以下方式实现的
访问edge_array[vertex_array[i]]，
边数组[顶点数组[i]+1], ...,
边数组[顶点数组[i+1]]。这
格式将内存使用最小化至 O(n +
m)，其中 n 和 m 是
分别是顶点和边。这
常数乘以 n 和 m 为
基于整数的大小
需要表示索引
分别是边和顶点数组（...）

这里是偏移数组的一个很好的解释：

 偏移邻居
   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 字段。这指向下一个边缘。

来自同一来源：

 偏移节点下一个
   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

If you don't need to modify your graph after creation, take a look at the compressed sparse row (CSR) format. A description from BGL:

The CSR format stores vertices and
edges in separate arrays, with the
indices into these arrays
corresponding to the identifier for
the vertex or edge, respectively. The
edge array is sorted by the source of
each edge, but contains only the
targets for the edges. The vertex
array stores offsets into the edge
array, providing the offset of the
first edge outgoing from each vertex.
Iteration over the out-edges for the
ith vertex in the graph is achieved by
visiting edge_array[vertex_array[i]],
edge_array[vertex_array[i]+1], ...,
edge_array[vertex_array[i+1]]. This
format minimizes memory use to O(n +
m), where n and m are the number of
vertices and edges, respectively. The
constants multiplied by n and m are
based on the size of the integers
needed to represent indices into the
edge and vertex arrays, respectively(...)

Here is a good explanation of Offset Arrays:

       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

Efficient Insertion of Edges

Allowing to insert edges after creation can be achieved by essentially making the Neighbours array into a "linked-list". The offset points
into the first neighbour, and each neighbour contains a Next field. This points to the next edge.

From the same source:

        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

回复收藏 0 原文