274
个编辑
更改
跳到导航
跳到搜索
第254行：
第254行： − + − + 第262行：
第262行： − 然而，对于一个稀疏的图，邻接表需要较少的空间，因为他们不浪费任何空间来表示边不存在。在32位计算机上使用一个天真的数组实现，一个无向图的邻接表需要大约 = 8}字节的空间，其中}是图的边数。+
→Data structures
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only <sup>2</sup>/8}} bytes of contiguous space, where }} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only <sup>2</sup>/8}} bytes of contiguous space, where }} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只需要一位，所以它可以用非常紧凑的方式表示图，只占用连续空间的 < sup > 2 </sup >/8}字节，其中}}是图的顶点数。除了避免浪费空间，这种紧凑性鼓励访问局部性。
'''<font color="32CD32">作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只需要一位，所以它可以用非常紧凑的方式表示图，只占用连续空间的 < sup > 2 </sup >/8}字节，其中}}是图的顶点数。除了避免浪费空间，这种紧凑性鼓励访问局部性。</font>'''For use as a data structure, the main alternative to the adjacency list is the adjacency matrix. Because each entry in the adjacency matrix requires only one bit, it can be represented in a very compact way, occupying only <sup>2</sup>/8}} bytes of contiguous space, where }} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
--该句空间占用怎么翻译
However, for a sparse graph, adjacency lists require less space, because they do not waste any space to represent edges that are not present. Using a naïve array implementation on a 32-bit computer, an adjacency list for an undirected graph requires about = 8}} bytes of space, where }} is the number of edges of the graph.
However, for a sparse graph, adjacency lists require less space, because they do not waste any space to represent edges that are not present. Using a naïve array implementation on a 32-bit computer, an adjacency list for an undirected graph requires about = 8}} bytes of space, where }} is the number of edges of the graph.
然而，对于一个稀疏的图，邻接表只需要较少的空间，因为它不浪费任何空间来表示边不存在。在32位计算机上使用一个简单的数组实现，一个无向图的邻接表需要大约 = 8}字节的空间，其中}是图的边数。