邻接表 - 版本历史

Qige96：/* 权衡 */

2021-01-21T08:50:22Z

权衡

思无涯咿呀咿呀：/* 操作 */

2021-01-20T12:30:43Z

操作

薄荷：/* 参见 */

2020-12-27T15:17:37Z

参见

2020年11月8日 (日) 11:23 薄荷

2020-11-08T11:23:44Z

薄荷：/* 实现 */

2020-11-08T11:23:20Z

实现

薄荷：/* 数据结构 */

2020-11-08T11:22:49Z

数据结构

薄荷：/* 数据结构 */

2020-11-08T11:22:29Z

数据结构

薄荷：/* 数据结构 */

2020-11-08T11:21:33Z

数据结构

薄荷：/* 数据结构 */

2020-11-08T11:21:06Z

数据结构

薄荷：/* 数据结构 */

2020-11-08T11:20:42Z

数据结构

@@ 第42行： / 第42行： @@
 ==权衡==
+'''邻接表'''的主要替代方法是'''[[邻接矩阵|邻接矩阵 Adjacency Matrix]]'''，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于'''<font color="#ff8000">稀疏图 Sparse Graph </font>'''（大多数顶点对不是由边连接的图），邻接表比邻接矩阵（存储为二维数组）更节省空间：邻接表的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的哈希表而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配邻接表的线性空间使用。
 '''邻接表'''和'''邻接矩阵'''之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。此外，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻；邻接表支持这一操作的速度较慢。
 <br>
 ==数据结构==

@@ 第33行： / 第33行： @@
 ==操作==
-接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点 ''v'' 所有邻居的总时间与 ''v'' 的'''<font color="#ff8000">度 Degree </font>'''成正比。
+邻接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何一种表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点 <math>''v'' </math>所有邻居的总时间与 <math>''v'' </math>的'''[[度]] Degree '''成正比。
-也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行'''<font color="#ff8000">顺序搜索 sequential search</font>'''，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用'''<font color="#ff8000">二分搜索法 binary search</font>'''，时间与次数的对数成正比。
+也可以使用邻接表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行'''<font color="#ff8000">顺序搜索 sequential search</font>'''，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用'''<font color="#ff8000">二分搜索法 binary search</font>'''，时间与次数的对数成正比。
 <br>
 ==权衡==

@@ 第81行： / 第81行： @@
 <br>
 ----
 本中文词条由[[用户:923397935|923397935]]参与编译，[[用户:黄秋莉|黄秋莉]]审校，[[用户:Banditwen|Banditwen]]、[[用户:薄荷|薄荷]]编辑，欢迎在讨论页面留言。

@@ 第5行： / 第5行： @@
 在[[图论]]和[[计算机科学]]中，'''邻接表 Adjacency List'''是用来表示'''有限图 '''的无序表的集合。每个列表描述图中一个顶点的邻域集。这是计算机程序中常用的几种图形表示法之一。
-[[文件:Simple cycle graph.svg.png|right|缩略图|此无向循环图可以用三个无序列表来描述:{a,b},{a,c},{b,c}]]
+[[文件:Simple cycle graph.svg.png|right|缩略图|此无向循环图可以用三个无序列表来描述：{a,b},{a,c},{b,c}]]
 ==实现==

@@ 第27行： / 第27行： @@
-*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.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.
+*Goodrich和Tamassia提出的面向对象入射列表结构有特殊的顶点对象和边缘对象类。每个顶点对象都有一个实例变量，指向一个集合对象，该集合对象列出了邻近的边缘对象。反过来，每个边缘对象又指向其端点的两个顶点对象。<ref name="A">{{cite book| author = Michael T. Goodrich and Roberto Tamassia | title = Algorithm Design: Foundations, Analysis, and Internet Examples| publisher = John Wiley & Sons | year = 2002  | isbn = 0-471-38365-1}}</ref> 这种表示方式邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
-Goodrich和Tamassia提出的面向对象入射列表结构有特殊的顶点对象和边缘对象类。每个顶点对象都有一个实例变量，指向一个集合对象，该集合对象列出了邻近的边缘对象。反过来，每个边缘对象又指向其端点的两个顶点对象。<ref name="A">{{cite book| author = Michael T. Goodrich and Roberto Tamassia | title = Algorithm Design: Foundations, Analysis, and Internet Examples| publisher = John Wiley & Sons | year = 2002  | isbn = 0-471-38365-1}}</ref> 这种表示方式邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
+<br>
 ==操作==

←上一版本		2020年11月8日 (日) 11:22的版本
第60行：		第60行：


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

	<br>		<br>

←上一版本		2020年11月8日 (日) 11:21的版本
第57行：		第57行：


−	注意到一个'''无向简单图'''最多可以有<math>（\|V\|^{2}-\|V\|）/2≈ V^{2}</math>条边(允许循环)，我们可以让<math>d = \|E\|/\|V\|^{2}</math>表示该图的密度。然后，当<math>8\|E\| > \|V\|^{2}/8</math>时，<math>\|E\|/\|V\|^{2}} > 1/64</math>，即<math>d = \|E\|/\|V\|^{2}}>1/64</math> ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。	+	注意到一个'''无向简单图'''最多可以有<math>（\|V\|^{2}-\|V\|）/2≈ V^{2}</math>条边(允许循环)，我们可以让<math>d = \|E\|/\|V\|^{2}</math>表示该图的密度。然后，当<math>8\|E\| > \|V\|^{2}/8</math>时，<math>\|E\|/\|V\|^{2} > 1/64</math>，即<math>d = \|E\|/\|V\|^{2}>1/64</math> ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。

@@ 第51行： / 第51行： @@
 ==数据结构==
-作为一种数据结构，邻接表的主要替代是邻接矩阵。因为邻接矩阵中的每个项只需要一个位，它可以用一种非常紧凑的方式表示，只占用<math>|V|^{2}/8</math>字节的连续空间，其中|V|是图的顶点数。除了避免浪费空间之外，这种紧凑性还支持'''<font color="#ff8000">局部引用 locality of reference</font>'''。
+作为一种数据结构，邻接表的主要替代是邻接矩阵。因为邻接矩阵中的每个项只需要一个位，它可以用一种非常紧凑的方式表示，只占用<math>|V|^{2}/8</math>字节的连续空间，其中<math>|V|</math>是图的顶点数。除了避免浪费空间之外，这种紧凑性还支持'''<font color="#ff8000">局部引用 locality of reference</font>'''。
-用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用 2·(32/8)|E| = 8|E| 字节的存储空间，其中|E|表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。
+用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用<math> 2·(32/8)|E|= 8 |E|</math>字节的存储空间，其中<math>|E|</math>表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。
-注意到一个'''无向简单图'''最多可以有(|V|2-|V|)/2 ≈ V <sup>2</sup>边(允许循环)，我们可以让'' d ''= |E|/|V|2表示该图的密度。然后，当|E|/|V|2 > 1/64时，8|E| > |V|2/8 ,即当d = |E|/|V|2 ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
+注意到一个'''无向简单图'''最多可以有<math>（|V|^{2}-|V|）/2≈ V^{2}</math>条边(允许循环)，我们可以让<math>d = |E|/|V|^{2}}</math>表示该图的密度。然后，当<math>8|E| > |V|^{2}/8</math>时，<math>|E|/|V|^{2}} > 1/64</math>，即<math>d = |E|/|V|^{2}}>1/64</math> ,邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。