更改

邻接表 (查看源代码)

2020年10月21日 (三) 17:00的版本

删除569字节、 2020年10月21日 (三) 17:00

无编辑摘要

第5行：第5行： −

在'''图论''和'''计算机科学'''中，'''邻接表 Adjacency List '''是用来表示'''有限图'''的无序表的集合。每个列表描述图中一个顶点的邻域集。这是计算机程序中常用的几种图形表示法之一。

+

在'''图论和'''计算机科学'''中，'''邻接表 Adjacency List '''是用来表示'''有限图'''的无序表的集合。每个列表描述图中一个顶点的邻域集。这是计算机程序中常用的几种图形表示法之一。

==实现==

第118行：第118行： −

~~邻接表的主要替代方法是~~'''邻接矩阵 Adjacency Matrix '''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''稀疏图 Sparse Graph '''（大多数顶点对不是由边连接的图），邻接表比邻接矩阵（存储为二维数组）更节省空间：邻接表的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的哈希表而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配邻接表的线性空间使用。

+

'''邻接表'''的主要替代方法是'''邻接矩阵 Adjacency Matrix '''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''稀疏图 Sparse Graph '''（大多数顶点对不是由边连接的图），'''邻接表'''比邻接矩阵（存储为二维数组）更节省空间：'''邻接表'''的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的'''哈希表'''而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配'''邻接表'''的线性空间使用。

−

~~--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“邻接表”改为~~'''邻接表'''~~；“哈希表”改为~~'''哈希表'''

+

'''邻接表'''和'''邻接矩阵'''之间的另一个显著区别是它们执行操作的效率。在'''邻接表'''中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在'''邻接矩阵'''中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，'''邻接矩阵'''允许测试两个顶点是否在固定的时间内彼此相邻; '''邻接表'''支持这一操作的速度较慢。

+

−

邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻; 邻接表支持这一操作的速度较慢。

+

==数据结构==

−

~~--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“邻接表”改为'''邻接表'''；“邻接矩阵”改为'''邻接矩阵'''~~

−

~~==Data structures~~==

数据结构

+

'''作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的2/8}}字节，其中}}是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用。'''

−

'''作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只需要一位，所以它可以用非常紧凑的方式表示图，只占用连续空间的 2 /8}字节，其中}}是图的顶点数。除了避免浪费空间，这种紧凑性鼓励访问局部性。'''

−

~~--该句空间占用怎么翻译~~

−

--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的2/8}}字节，其中}}是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用。

--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}}是图的顶点数”中的“}}”不清楚是什么

−

然而，对于一个稀疏的图，邻接表只需要较少的空间，因为它不浪费任何空间来表示边不存在。在32位计算机上使用一个简单的数组实现，一个无向图的邻接表需要大约 = 8}字节的空间，其中}是图的边数。

--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“其中}是图的边数”中的“}”不清楚是什么

−

+

注意到一个'''无向简单图'''最多可以有 2 -)/2≈ v 2 }边，允许循环，我们可以让/ 2 }表示该图的密度。然后，> 2 /8}当/ 2 > 1/64}时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。

−

~~注意到一个无向简单图最多可以有~~ 2 -)/2≈ v 2 }边，允许循环，我们可以让/ 2 }表示该图的密度。然后，> 2 /8}当/ 2 > 1/64}时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。

−

~~--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“无向简单图”改为'''无向简单图'''~~

−

除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。

第151行：第142行：

−

Banditwen

11

个编辑