11
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − 此词条暂由彩云小译翻译，未经人工整理和审校，带来阅读不便，请见谅。<br>+ − 本词条由信白初步翻译<br> − [[Image:Simple cycle graph.svg|thumb|120px|This undirected cyclic graph can be described by the three unordered lists {{nowrap|{b, c}}}, {{nowrap|{a, c}}}, {{nowrap|{a, b}}}.]] − This undirected cyclic graph can be described by the three unordered lists }, }, }. 第11行：
第8行： − In [[graph theory]] and [[computer science]], an '''adjacency list''' is a collection of unordered lists used to represent a finite [[Graph (discrete mathematics)|graph]]. Each list describes the set of neighbors of a [[Vertex (graph theory)|vertex]] in the graph. This is one of several commonly used representations of [[Graph (abstract data type)|graphs]] for use in computer programs. − − In graph theory and computer science, an adjacency list is a collection of unordered lists used to represent a finite graph. Each list describes the set of neighbors of a vertex in the graph. This is one of several commonly used representations of graphs for use in computer programs. 第19行：
第13行： − + − 实施细则+ 第76行：
第70行： − − An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighboring vertices or edges. There are many variations of this basic idea, differing in the details of how they implement the association between vertices and collections, in how they implement the collections, in whether they include both vertices and edges or only vertices as first class objects, and in what kinds of objects are used to represent the vertices and edges. − − An adjacency list representation for a graph associates each vertex in the graph with the collection of its neighboring vertices or edges. There are many variations of this basic idea, differing in the details of how they implement the association between vertices and collections, in how they implement the collections, in whether they include both vertices and edges or only vertices as first class objects, and in what kinds of objects are used to represent the vertices and edges. 第179行：
第169行： − − }}</ref> Their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a [[singly linked list]] of the neighboring vertices of that vertex. In this representation, the nodes of the singly linked list may be interpreted as edge objects; however, they do not store the full information about each edge (they only store one of the two endpoints of the edge) and in undirected graphs there will be two different linked list nodes for each edge (one within the lists for each of the two endpoints of the edge). − − }}</ref> Their representation uses an array indexed by vertex number, in which the array cell for each vertex points to a singly linked list of the neighboring vertices of that vertex. In this representation, the nodes of the singly linked list may be interpreted as edge objects; however, they do not store the full information about each edge (they only store one of the two endpoints of the edge) and in undirected graphs there will be two different linked list nodes for each edge (one within the lists for each of the two endpoints of the edge). − + − *The [[object oriented]] incidence list structure suggested by Goodrich and Tamassia has special classes of vertex objects and edge objects. Each vertex object has an instance variable pointing to a collection object that lists the neighboring edge objects. In turn, each edge object points to the two vertex objects at its endpoints.<ref name="A">{{cite book − --[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】Goodrich & Tamassia提出的'''<font color="#ff8000">面向对象</font>'''关联列表结构具有特殊类的顶点对象和边对象。每个顶点对象都有一个实例变量，指向列出相邻边对象的集合对象。反过来，每个边对象都指向其端点处的两个顶点对象。 第223行：
第207行： − 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 of v. − − 邻接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点 ''v'' 所有邻居的总时间与 ''v'' 的'''<font color="#ff8000">度 Degree </font>'''成正比。 − − − − It is also possible, but not as efficient, to use adjacency lists to test whether an edge exists or does not exist between two specified vertices. In an adjacency list in which the neighbors of each vertex are unsorted, testing for the existence of an edge may be performed in time proportional to the minimum degree of the two given vertices, by using a [[sequential search]] through the neighbors of this vertex. If the neighbors are represented as a sorted array, [[binary search]] may be used instead, taking time proportional to the logarithm of the degree. − − It is also possible, but not as efficient, to use adjacency lists to test whether an edge exists or does not exist between two specified vertices. In an adjacency list in which the neighbors of each vertex are unsorted, testing for the existence of an edge may be performed in time proportional to the minimum degree of the two given vertices, by using a sequential search through the neighbors of this vertex. If the neighbors are represented as a sorted array, binary search may be used instead, taking time proportional to the logarithm of the degree. 第240行：
第215行： − 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 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 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. 第257行：
第227行： − 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 <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.”。+ − 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 = 8}} bytes of space, where }} is the number of edges of the graph. − − Noting that an undirected simple graph can have at most {{math|({{abs|''V''}}<sup>2</sup>-{{abs|''V''}})/2 ≈ ''V''<sup> 2</sup>}} edges, allowing loops, we can let {{math|1=''d'' = {{abs|''E''}}/{{abs|''V''}}<sup>2</sup>}} denote the density of the graph. Then, {{math|8{{abs|''E''}} > {{abs|''V''}}<sup>2</sup>/8}} when {{math|{{abs|''E''}}/{{abs|''V''}}<sup>2</sup> > 1/64}}, that is the adjacency list representation occupies more space than the adjacency matrix representation when {{math|''d'' > 1/64}}. Thus a graph must be sparse enough to justify an adjacency list representation. − − Noting that an undirected simple graph can have at most <sup>2</sup>-)/2 ≈ V<sup> 2</sup>}} edges, allowing loops, we can let /<sup>2</sup>}} denote the density of the graph. Then, > <sup>2</sup>/8}} when /<sup>2</sup> > 1/64}}, that is the adjacency list representation occupies more space than the adjacency matrix representation when . Thus a graph must be sparse enough to justify an adjacency list representation. − − Besides the space trade-off, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list. With an adjacency matrix, an entire row must instead be scanned, which takes {{math|''O''({{abs|''V''}})}} time. Whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list. − − Besides the space trade-off, the different data structures also facilitate different operations. Finding all vertices adjacent to a given vertex in an adjacency list is as simple as reading the list. With an adjacency matrix, an entire row must instead be scanned, which takes )}} time. Whether there is an edge between two given vertices can be determined at once with an adjacency matrix, while requiring time proportional to the minimum degree of the two vertices with the adjacency list.
无编辑摘要
{{short description|Data structure representing a graph}}
{{short description|Data structure representing a graph}}
图：这个无向循环图可以用三个无序列表来描述。
图：这个无向循环图可以用三个无序列表来描述。
在图论和计算机科学中，'''<font color="#ff8000">邻接表 Adjacency List </font>'''是用来表示有限图的无序表的集合。每个列表描述图中一个顶点的邻居集合。这是计算机程序中常用的几种图形表示法之一。
在图论和计算机科学中，'''<font color="#ff8000">邻接表 Adjacency List </font>'''是用来表示有限图的无序表的集合。每个列表描述图中一个顶点的邻居集合。这是计算机程序中常用的几种图形表示法之一。
==Implementation details==
==实现==
实现
{| class = "wikitable" align="right" style="width:18em;"
{| class = "wikitable" align="right" style="width:18em;"
图的邻接表表示法将图中的每个顶点与其邻接顶点或边的集合关联起来。这个基本思想有许多变体，在如何实现顶点和集合之间的关联，如何实现集合，以及是否包括顶点和边还是只包括顶点作为第一类对象，以及什么类型的对象被用来表示顶点和边的细节上都有所不同。
图的邻接表表示法将图中的每个顶点与其邻接顶点或边的集合关联起来。这个基本思想有许多变体，在如何实现顶点和集合之间的关联，如何实现集合，以及是否包括顶点和边还是只包括顶点作为第一类对象，以及什么类型的对象被用来表示顶点和边的细节上都有所不同。
| authorlink4 = Clifford Stein
| authorlink4 = Clifford Stein
它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<font color="#ff8000">无向图 Undirected Graph </font>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。
它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<font color="#ff8000">无向图 Undirected Graph </font>'''中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】Goodrich & Tamassia提出的'''<font color="#ff8000">面向对象</font>'''关联列表结构具有特殊类的顶点对象和边对象。每个顶点对象都有一个实例变量，指向列出相邻边对象的集合对象。反过来，每个边对象都指向其端点处的两个顶点对象。
| author = [[Michael T. Goodrich]] and [[Roberto Tamassia]]
| author = [[Michael T. Goodrich]] and [[Roberto Tamassia]]
操作
操作
接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点 ''v'' 所有邻居的总时间与 ''v'' 的'''<font color="#ff8000">度 Degree </font>'''成正比。
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。
权衡
权衡
邻接表的主要替代方法是'''<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>'''
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“邻接表”改为'''<font color="#ff8000">邻接表</font>'''；“哈希表”改为'''<font color="#ff8000">哈希表</font>'''
邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻; 邻接表支持这一操作的速度较慢。
邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻; 邻接表支持这一操作的速度较慢。
数据结构
数据结构
'''<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>'''
--该句空间占用怎么翻译
--该句空间占用怎么翻译
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的<sup>2</sup>/8}}字节，其中}}是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的<sup>2</sup>/8}}字节，其中}}是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}}是图的顶点数”中的“}}”不清楚是什么
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}}是图的顶点数”中的“}}”不清楚是什么
然而，对于一个稀疏的图，邻接表只需要较少的空间，因为它不浪费任何空间来表示边不存在。在32位计算机上使用一个简单的数组实现，一个无向图的邻接表需要大约 = 8}字节的空间，其中}是图的边数。
然而，对于一个稀疏的图，邻接表只需要较少的空间，因为它不浪费任何空间来表示边不存在。在32位计算机上使用一个简单的数组实现，一个无向图的邻接表需要大约 = 8}字节的空间，其中}是图的边数。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}是图的边数”中的“}”不清楚是什么
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}是图的边数”中的“}”不清楚是什么
注意到一个无向简单图最多可以有 < sup > 2 </sup > -)/2≈ v < sup > 2 </sup > }边，允许循环，我们可以让/< sup > 2 </sup > }表示该图的密度。然后，> < sup > 2 </sup >/8}当/< sup > 2 </sup > > 1/64}时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
注意到一个无向简单图最多可以有 < sup > 2 </sup > -)/2≈ v < sup > 2 </sup > }边，允许循环，我们可以让/< sup > 2 </sup > }表示该图的密度。然后，> < sup > 2 </sup >/8}当/< sup > 2 </sup > > 1/64}时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“无向简单图”改为'''<font color="#ff8000">无向简单图</font>'''
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“无向简单图”改为'''<font color="#ff8000">无向简单图</font>'''
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。