邻接表

图的邻接表表示将图中的每个顶点与其相邻顶点或边的集合做关联。这一基本思想有许多变体，不同之处在于它们如何实现顶点和集合之间的关联、它们如何实现相邻顶点或边的集合、它们是同时包括顶点和边还是仅包括顶点并把它作为第一类对象，以及用什么样的对象来表示顶点和边。

• 吉多·范·罗苏姆建议的一种实现是使用散列表将图中的每个顶点与相邻顶点的数组做关联。在这个表示方法中，顶点可以由任何可散列的对象来表示。这种实现方法中没有将边明确表示为对象。^[1]
• Cormen等人提出了一种实现方法，其中顶点由索引号表示。^[2] 他们的表示方法使用一个按顶点数索引的数组，其中每个顶点的数组单元指向该顶点的相邻顶点的单链表。在该表示方法中，单链表的节点可以被解释为边的对象；但是，它们并不存储关于每条边的全部信息(它们只存储边的两个端点之一)，并且在无向图中，每条边将有两个不同的链表节点(边的两个端点的列表中各有一个)。
• 古德里奇和塔马西亚提出的面向对象关联列表结构用特殊类来表示顶点对象和边对象。每个顶点对象都有一个实例变量，该变量指向一个集合对象，该集合内列出了邻接边对象。反之，每个边对象在其端点指向两个顶点对象。^[3] 邻接表的这个实现版本比直接列出相邻顶点的版本占用更多的内存，但是显式边对象的存在使它在存储关于边的附加信息时具有额外的灵活性。

邻接表数据结构执行的主要操作是给出给定顶点的邻接点列表。使用上面详述的任何实现方法，每个邻接点的该操作都可以在常数时间内完成。换句话说，给出顶点v的所有邻接点的总时间与顶点v的度成比例。

使用邻接表来测试两个指定顶点之间是否存在边也是可能的，但效率不高。在每个顶点的所有邻接点都未经排序的邻接表中，因为要对该顶点的邻接点集合使用顺序搜索，所以测试是否存在边的时间是与这两个给定顶点的度中较小的那个成正比。如果邻接点是有序的，则可以使用二分搜索来代替线性搜索，所花费的时间与顶点的度的对数成正比。

邻接表的主要替代实现方法是邻接矩阵，这是行和列的索引为顶点一种矩阵，并且每个单元格中储存着一个布尔值，该布尔值表示与单元格的行和列相对应的顶点之间是否存在边。对于稀疏图而言(其中大多数顶点对都是没有边相连的图)，邻接表比邻接矩阵(存储为数组时)更节省空间：邻接表的空间使用与图中边和顶点的数量成正比，而对于以这种数组方式存储的邻接矩阵而言，空间与顶点数量的平方成正比。然而， 通过使用相连的顶点对的哈希表，而不是数组来储存邻接矩阵，可以使得邻接矩阵的储存更高效，可以获得与邻接表相似的线性空间使用率。

邻接表和邻接矩阵之间的另一个显著区别是它们执行操作的效率。在邻接表中，每个顶点的邻接点可以被高效地列出，在时间上与顶点的度成正比。在邻接矩阵中，该操作需要的时间与图中顶点的数量成正比，这可能明显高于度。另一方面，邻接矩阵可以在常数时间内测试两点是否相连；而邻接表进行此操作的速度较慢。

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

然而，对于稀疏图而言，邻接表需要更少的空间，因为它们不会浪费任何空间来表示不存在的边。在32位计算机上使用简单的数组实现时，无向图的邻接表需要大约2·(32/8)|E| = 8|E| 字节的空间，其中 |E|是图的边数。

注意，一个无向简单图在允许出现环的情况下最多可以有 (|V|²-|V|)/2 ≈ V ²条边，我们可以让d = |E|/|V|²表示图的密度。然后，当8|E| > |V|²/8时， |E|/|V|² > 1/64，即d > 1/64时，邻接表比邻接矩阵占用更多的空间。因此，一个图必须足够稀疏，以证明邻接表表示的合理性（邻接表表示才是合理的）。

除了空间上的权衡之外，不同的数据结构也便于不同的操作。在邻接表中查找与给定顶点相邻的所有顶点就像读取列表一样简单。使用邻接矩阵，必须扫描整行，这需要O(|V|)时间。在确定两个给定顶点之间是否有边可以用邻接矩阵一次确定，然而在邻接表中则需要与两个顶点的较小度成正比的时间。