1. 邻接表

所谓邻接表，就是把从同一个顶点发出的边链接在同一个称为边链表的单链表中。边链表的每个结点代表一条边，称为边结点。每个边结点有 2 个域：该边终点的序号，以及指向下一个边结点的指针。在邻接表中，还需要一个用于存储顶点信息的顶点数组。 

例如，如下所示的有向图对应的邻接表如图(b)所示。在顶点数组中，每个元素有两个成员：一个成员用来存储顶点信息；另一个成员为该顶点的边链表的表头指针，指向该顶点的边链表。如果没有从某个顶点发出的边，则该顶点没有边链表，因此表头指针为空，如图(b)中的顶点 G。在该图中，如果指针为空，则用符号“∧”表示。 

在邻接表每个顶点的边链表中，各边结点所表示的边都是从该顶点发出的边，因此这种邻接表也称为出边表。采用邻接表存储图时，求顶点的出度很方便，只需要统计每个顶点的边链表中边结点的个数即可，但在求顶点的入度时就比较麻烦。

如果需要统计各顶点的入度，可以采用逆邻接表存储表示图。所谓逆邻接表，也称为入边表，就是把进入同一个顶点的边链接在同一个边链表中。 

因为无向图中的边没有方向性，所以无向图的邻接表没有入边表和出边表之分。在无向图的邻接表中，与顶点 v 相关联的边都链接到该顶点的边链表中。无向图的每条边在邻接表里出现 2次。 

说明：如果用邻接表存储有向网或无向网，则在边结点中还应增加一个成员，用于存储边的权值。 

2.  存储方式对算法复杂度的影响

时间复杂度：邻接表里直接存储了边的信息，浏览完所有的边，对有向图来说，时间复杂度复杂度是 O(m)， 对无向图是 O(2×m)。 而邻接矩阵是间接存储边， 浏览完所有的边， 复杂度是 O(n2)。

空间复杂度：邻接表里除了存储 m 条边所对应的边结点外，还需要一个顶点数组，存储各顶点的顶点信息及各边链表的表头指针，总的空间复杂度为 O(n+m)（或 O(n+2m)）；而用邻接矩阵存储图，需要 n×n 规模的存储单元，其空间复杂度为 O(n2)。当边的数目相对于 n×n 比较小时，邻接矩阵里存储了较多的无用信息，用邻接表可以节省较多的存储空间。