11
个编辑
更改
跳到导航
跳到搜索
第1行：
第1行： − − {{short description|Data structure representing a graph}} − − 第108行：
第104行： − 算法导论，第二版 − --[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】|标题 = 《算法导论》，第二版 − | publisher = MIT Press and McGraw-Hill − − | publisher = MIT Press and McGraw-Hill − − | publisher = MIT Press and McGraw-Hill − --[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】|出版社 = MIT Press and McGraw-Hill − | year = 2001 − − | year = 2001 − − 2001年 − − | isbn = 0-262-03293-7 − − | isbn = 0-262-03293-7 − − | isbn = 0-262-03293-7 − − | pages = 527–529 of section 22.1: Representations of graphs| name-list-format=vanc − − | pages = 527–529 of section 22.1: Representations of graphs| name-list-format=vanc − − | pages = 527-529 of section 22.1: representation of graphs | name-list-format = vanc − − |author1 = Thomas H. Cormen|author2 = Charles E. Leiserson| author3 = Ronald L. Rivest − − |author1 = Thomas H. Cormen|author2 = Charles E. Leiserson| author3 = Ronald L. Rivest − − |author1 = 托马斯·科尔曼 | author2 = 查尔斯·雷瑟尔森 | author3 = 罗纳德·李维斯特 − − | author4 = Clifford Stein − − | author4 = Clifford Stein − − |author4 = Clifford Stein − − | authorlink1 = Thomas H. Cormen − − | authorlink1 = Thomas H. Cormen − − |authorlink1 = 托马斯·科尔曼 − − | authorlink2 = Charles E. Leiserson − − | authorlink2 = Charles E. Leiserson − − |authorlink2 = 查尔斯·雷瑟尔森 − − | authorlink3 = Ronald L. Rivest − − | authorlink3 = Ronald L. Rivest − − |authorlink3 = 罗纳德·李维斯特 − − | authorlink4 = Clifford Stein − − | authorlink4 = Clifford Stein − − | authorlink4 = Clifford Stein − − 它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在'''<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 − − | 作者: Michael t. Goodrich and Roberto Tamassia − − | title = Algorithm Design: Foundations, Analysis, and Internet Examples − − | title = Algorithm Design: Foundations, Analysis, and Internet Examples − − | title = 算法设计: 基础、分析和互联网示例 − − | publisher = John Wiley & Sons − − | publisher = John Wiley & Sons − − | publisher = 约翰威立 − − | year = 2002 − − | year = 2002 − − | 2002年 − − | 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. + − + 第212行：
第116行： − + 第246行：
第150行： − + 第252行：
第156行： − + 第282行：
第186行： − +
无编辑摘要
图：这个无向循环图可以用三个无序列表来描述。
图：这个无向循环图可以用三个无序列表来描述。
| title = Introduction to Algorithms, Second Edition
| title = Introduction to Algorithms, Second Edition
这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
==Operations==
==操作==
操作
操作
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。
==Trade-offs==
==权衡==
权衡
权衡
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费)}的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“这需要花费)}的时间”中“)}”不知道是什么内容
--[[用户：黄秋莉|黄秋莉]][[用户讨论：黄秋莉|讨论]] 【审校】“这需要花费)}的时间”中“)}”不知道是什么内容
==References==
==参考资料==
{{reflist}}
{{reflist}}
==Further reading==
==延伸阅读==
* {{cite web
* {{cite web
==External links==
==其他链接==
{{commons category|Adjacency list}}
{{commons category|Adjacency list}}