邻接表
图：这个 无向循环图可以用三个无序列表来描述。
在图论和计算机科学中，邻接表 Adjacency List 是用来表示有限图的无序表的集合。每个列表描述图中一个顶点的邻域集。这是计算机程序中常用的几种图形表示法之一。
实现
| 上图中的图表有这样的邻接表示法: | ||
| a | 毗邻 | b，c |
| b | 毗邻 | a，c |
| 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
这个版本的邻接表比直接列出相邻顶点的版本使用更多的内存，但是显示边对象的存在操作可以允许它在存储额外的关于边的信息方面有额外的灵活性。
操作
操作
接表数据结构执行的主要操作是列出给定顶点的邻居列表。使用上面详细说明的任何表示方式，都可以在每个邻居的固定时间内执行。换句话说，列出一个顶点 v 所有邻居的总时间与 v 的度 Degree 成正比。
也可以使用邻接列表来测试两个指定顶点之间是否存在边，但效率不高。在一个邻接表中，每个顶点的邻域都是不排序的，通过对该顶点的邻域进行顺序搜索，可以按照给定两个顶点的最小阶数按时间比例进行边的存在性测试。如果邻域被表示为一个排序数组，则可以使用二进制搜索，时间与次数的对数成正比。
权衡
权衡
邻接表的主要替代方法是邻接矩阵 Adjacency Matrix ，该矩阵的行和列按顶点索引，其单元格包含一个布尔值，该值指示与单元格的行和列对应的顶点之间是否存在边。对于稀疏图 Sparse Graph （大多数顶点对不是由边连接的图），邻接表比邻接矩阵（存储为二维数组）更节省空间：邻接表的空间使用与图中的边和顶点的数量成正比，而对于以这种方式存储的邻接矩阵，其空间与顶点数的平方成正比。然而，通过使用由顶点对索引的哈希表而不是数组，可以更有效地存储邻接矩阵的空间，从而匹配邻接表的线性空间使用。
邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻居可以有效地列出，在时间上与顶点的程度成正比。在邻接矩阵中，这个操作需要的时间与图中顶点的数量成正比，而顶点的数量可能明显高于度。另一方面，邻接矩阵允许测试两个顶点是否在固定的时间内彼此相邻; 邻接表支持这一操作的速度较慢。
数据结构
数据结构
作为一种数据结构，邻接表的主要替代方法是邻接矩阵。因为邻接矩阵中的每个条目只占一个比特(bit) ，所以它可以用非常紧凑的方式表示，只占用相邻空间的n2/8}}字节，其中n是图的顶点数。除了避免占用空间外，这种紧凑性还支持局部引用locality of reference。
用稀疏邻接矩阵表示邻接表时，将占用更少的空间。这是因为它能避免为不存在的边分配任何空间。在一台32位计算机上，如果使用原始的数组结构实现邻接表，那么对于一个无向图来说，它大约需要占用8e字节的存储空间，其中e表示边的个数。每条边都将会在两个邻接表中重复出现，并分别占用4字节空间。
注意到一个无向简单图最多可以有 n2边(允许循环)，我们可以让d=e/n2表示该图的密度。然后，8e>n2/8当d>1/64时，即邻接表表示比邻接矩阵表示占用更多的空间。因此，图必须足够稀疏，才适合使用邻接表表示。
除了空间上的权衡，不同的数据结构也有着不同的操作。在邻接表中找到与给定顶点相邻的所有顶点就像读取邻接表一样简单。对于邻接矩阵，必须扫描整行，这需要花费O(n)的时间。给定的两个顶点之间是否有边可以用邻接矩阵一次确定，并且运行时间与邻接列表中两个顶点的最小度数成正比。
参考资料
延伸阅读
- 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
其他链接
- The Boost Graph Library implements an efficient adjacency list
Category:Graph data structures
类别: 图形数据结构
This page was moved from wikipedia:en:Adjacency list. Its edit history can be viewed at 邻接矩阵/edithistory