邻接表

来自集智百科 - 复杂系统|人工智能|复杂科学|复杂网络|自组织
Banditwen（讨论 | 贡献）2020年10月21日 (三) 15:08的版本
跳到导航 跳到搜索


图：这个无向循环图可以用三个无序列表来描述。 

 --黄秋莉（讨论） 【审校】“无向循环图”改为 无向循环图。


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

 --黄秋莉讨论  【审校】“图论”改为图论;“计算机科学”改为计算机科学；“有限图”改为有限图；“每个列表描述图中一个顶点的邻居集合。”改为“每个列表描述图中一个顶点的邻域集”。


实现

实现

{ | class = “ wikitable” align = “ right” style = “ width: 18em; ”
The graph pictured above has this adjacency list representation: The graph pictured above has this adjacency list representation: 上图中的图表有这样的邻接表示法:
a adjacent to b,c a adjacent to b,c

靠近 b 和 c 

 --黄秋莉讨论  【审校】“靠近 b 和 c”改为a | |毗邻| | b，c
b adjacent to a,c b adjacent to a,c 
 --黄秋莉讨论  【审校】b | |毗邻| |a，c
c adjacent to a,b c adjacent to a,b

靠近 a 和 b 

 --黄秋莉讨论  【审校】“靠近 a 和 b”改为c | |毗邻| |a，b

|}


图的邻接表表示法将图中的每个顶点与其邻接顶点或边的集合关联起来。这个基本思想有许多变体，在如何实现顶点和集合之间的关联，如何实现集合，以及是否包括顶点和边还是只包括顶点作为第一类对象，以及什么类型的对象被用来表示顶点和边的细节上都有所不同。

  • An implementation suggested by Guido van Rossum uses a hash table to associate each vertex in a graph with an array of adjacent vertices. In this representation, a vertex may be represented by any hashable object. There is no explicit representation of edges as objects.
 --黄秋莉讨论  【审校】* 吉多·范罗苏姆（Guido van Rossum）提出一种实现方法：哈希表，将图中的每个顶点与其相邻顶点采用一种数组数据结构表示。在这种表示法中，顶点可以由任何散列对象表示，而连边没有被表示为对象。
 | author = Guido van Rossum

 | author = Guido van Rossum

作者: 吉多·范罗苏姆 

 --黄秋莉讨论  【审校】吉多·范罗苏姆（Guido van Rossum）

 | year = 1998

 | year = 1998

1998年 

 | title = Python Patterns — Implementing Graphs

 | title = Python Patterns — Implementing Graphs

| title = Python Patterns ーー实现图形 

 --黄秋莉讨论  【审校】“| title = Python Patterns ーー实现图形”改为“标题 = Python代码 --图形实现”
 | url = https://www.python.org/doc/essays/graphs/}}</ref>

 | url = https://www.python.org/doc/essays/graphs/}}</ref>

| url = https://www.python.org/doc/essays/graphs/} </ref >

  • Cormen et al. suggest an implementation in which the vertices are represented by index numbers.
 --黄秋莉讨论  【审校】Cormen等建议使用顶点索引号对顶点操作 
 | title = Introduction to Algorithms, Second Edition

 | title = Introduction to Algorithms, Second Edition

算法导论，第二版 

 --黄秋莉讨论  【审校】|标题 = 《算法导论》，第二版
 | 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

它们的表示使用一个按顶点数索引的数组，其中每个顶点的数组单元格指向该顶点的相邻顶点的单链表。在这种表示中，单链表的节点可以解释为边对象; 然而，它们并不存储关于每条边的完整信息(它们只存储边的两个端点中的一个) ，在无向图 Undirected Graph 中，每条边有两个不同的链表节点(边的两个端点中的每个端点的列表中都有一个)。

--黄秋莉讨论  【审校】Goodrich & Tamassia提出的面向对象关联列表结构具有特殊类的顶点对象和边对象。每个顶点对象都有一个实例变量，指向列出相邻边对象的集合对象。反过来，每个边对象都指向其端点处的两个顶点对象。

 | 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.

这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。

Operations

操作

接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点 v 所有邻居的总时间与 v 的度 Degree 成正比。


也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。

Trade-offs

权衡


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

 --黄秋莉讨论  【审校】“邻接表”改为邻接表；“哈希表”改为哈希表


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

 --黄秋莉讨论  【审校】“邻接表”改为邻接表；“邻接矩阵”改为邻接矩阵

Data structures

数据结构


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

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


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

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


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

 --黄秋莉讨论  【审校】“无向简单图”改为无向简单图


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

 --黄秋莉讨论  【审校】“这需要花费)}的时间”中“)}”不知道是什么内容

References


Further reading

  • David Eppstein

作者: David Eppstein (1996

1996年). "ICS 161 Lecture Notes: Graph Algorithms 161课堂笔记: 图形算法". {{cite web}}: Check date values in: |year= (help); line feed character in |author= at position 15 (help); line feed character in |title= at position 40 (help); line feed character in |year= at position 5 (help) 

 | url = http://www.ics.uci.edu/~eppstein/161/960201.html}}

Http://www.ics.uci.edu/~eppstein/161/960201.html


External links

模板:Commons category


模板:Graph representations

Category:Graph data structures

类别: 图形数据结构


This page was moved from wikipedia:en:Adjacency list. Its edit history can be viewed at 邻接矩阵/edithistory

取自“https://wiki.swarma.org/index.php?title=邻接表&oldid=16107”