29
个编辑
更改
跳到导航
跳到搜索
第217行：
第217行： − | 这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。+ + 第236行：
第237行： − + 第243行：
第244行： − + 第250行：
第251行： + − + 第260行：
第262行： − + + +
无编辑摘要
| isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.
| isbn = 0-471-38365-1}}</ref> This version of the adjacency list uses more memory than the version in which adjacent vertices are listed directly, but the existence of explicit edge objects allows it extra flexibility in storing additional information about edges.
这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
==Operations==
==Operations==
操作
操作
The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex. Using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the total time to report all of the neighbors of a vertex ''v'' is proportional to the [[degree (graph theory)|degree]] of ''v''.
The main operation performed by the adjacency list data structure is to report a list of the neighbors of a given vertex. Using any of the implementations detailed above, this can be performed in constant time per neighbor. In other words, the total time to report all of the neighbors of a vertex ''v'' is proportional to the [[degree (graph theory)|degree]] of ''v''.
==Trade-offs==
==Trade-offs==
权衡<br>
权衡
The main alternative to the adjacency list is the [[adjacency matrix]], a [[matrix (mathematics)|matrix]] whose rows and columns are indexed by vertices and whose cells contain a Boolean value that indicates whether an edge is present between the vertices corresponding to the row and column of the cell. For a [[sparse graph]] (one in which most pairs of vertices are not connected by edges) an adjacency list is significantly more space-efficient than an adjacency matrix (stored as a two-dimensional array): the space usage of the adjacency list is proportional to the number of edges and vertices in the graph, while for an adjacency matrix stored in this way the space is proportional to the square of the number of vertices. However, it is possible to store adjacency matrices more space-efficiently, matching the linear space usage of an adjacency list, by using a hash table indexed by pairs of vertices rather than an array.
The main alternative to the adjacency list is the [[adjacency matrix]], a [[matrix (mathematics)|matrix]] whose rows and columns are indexed by vertices and whose cells contain a Boolean value that indicates whether an edge is present between the vertices corresponding to the row and column of the cell. For a [[sparse graph]] (one in which most pairs of vertices are not connected by edges) an adjacency list is significantly more space-efficient than an adjacency matrix (stored as a two-dimensional array): the space usage of the adjacency list is proportional to the number of edges and vertices in the graph, while for an adjacency matrix stored in this way the space is proportional to the square of the number of vertices. However, it is possible to store adjacency matrices more space-efficiently, matching the linear space usage of an adjacency list, by using a hash table indexed by pairs of vertices rather than an array.
邻接表的主要替代方法是'''<font color="#ff8000">邻接矩阵 Adjacency Matrix </font>'''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''<font color="#ff8000">稀疏图 Sparse Graph </font>'''（大多数顶点对不是由边连接的图），邻接表比邻接矩阵（存储为二维数组）更节省空间：邻接表的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的哈希表而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配邻接表的线性空间使用。
邻接表的主要替代方法是'''<font color="#ff8000">邻接矩阵 Adjacency Matrix </font>'''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''<font color="#ff8000">稀疏图 Sparse Graph </font>'''（大多数顶点对不是由边连接的图），邻接表比邻接矩阵（存储为二维数组）更节省空间：邻接表的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的哈希表而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配邻接表的线性空间使用。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“邻接表”改为'''<font color="#ff8000">邻接表</font>'''；“哈希表”改为'''<font color="#ff8000">哈希表</font>'''
The other significant difference between adjacency lists and adjacency matrices is in the efficiency of the operations they perform. In an adjacency list, the neighbors of each vertex may be listed efficiently, in time proportional to the degree of the vertex. In an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree. On the other hand, the adjacency matrix allows testing whether two vertices are adjacent to each other in constant time; the adjacency list is slower to support this operation.
The other significant difference between adjacency lists and adjacency matrices is in the efficiency of the operations they perform. In an adjacency list, the neighbors of each vertex may be listed efficiently, in time proportional to the degree of the vertex. In an adjacency matrix, this operation takes time proportional to the number of vertices in the graph, which may be significantly higher than the degree. On the other hand, the adjacency matrix allows testing whether two vertices are adjacent to each other in constant time; the adjacency list is slower to support this operation.
邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻; 邻接表支持这一操作的速度较慢。
邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻; 邻接表支持这一操作的速度较慢。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“邻接表”改为'''<font color="#ff8000">邻接表</font>'''；“邻接矩阵”改为'''<font color="#ff8000">邻接矩阵</font>'''
==Data structures==
==Data structures==
数据结构<br>
数据结构
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 {{math|{{abs|''V''}}<sup>2</sup>/8}} bytes of contiguous space, where {{math|{{abs|''V''}}}} 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 {{math|{{abs|''V''}}<sup>2</sup>/8}} bytes of contiguous space, where {{math|{{abs|''V''}}}} is the number of vertices of the graph. Besides avoiding wasted space, this compactness encourages locality of reference.
'''<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.
'''<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.
--该句空间占用怎么翻译
--该句空间占用怎么翻译
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】删除英文“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.”。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的<sup>2</sup>/8}}字节，其中}}是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}}是图的顶点数”中的“}}”不清楚是什么
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 {{math|1=2·(32/8){{abs|''E''}} = 8{{abs|''E''}}}} bytes of space, where {{math|{{abs|''E''}}}} 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 {{math|1=2·(32/8){{abs|''E''}} = 8{{abs|''E''}}}} bytes of space, where {{math|{{abs|''E''}}}} is the number of edges of the graph.