5.2.2 邻接表法

当一个图为稀疏图时，使用邻接矩阵表示法显然要浪费大量的存储空间。而图的邻接表示法结合了顺序存储和链式存储方法，大大减少了这种不必要的浪费。

所谓邻接表就是对每个顶点vi建立一个单链表，第i个单链表中的结点表示依附于顶点vi的边（对于有向图则是以顶点vi为尾的弧），这个单链表就称为顶点vi的边表（对于有向图则成为出边表）。边表的头指针和顶点的数据信息采用顺序存储（称为顶点表），所以在邻接表中存在两种结点：顶点表结点和边表结点。

顶点表结点由顶点域（data）和指向第一条邻接边的指针（firstarc）构成

边表（邻接表）结点由结点域（adjvex）和指向下一条邻接边的指针域（nextarc）构成。

图的邻接表存储结构定义：

#define MaxVertexNum 100//顶点数目的最大值

typedef struct ArcNode{//边表结点
    int adjvex;//该弧所指向的顶点的位置
    struct ArcNode *next;//指向下一条弧的指针、
    InforType info;//网的边权值 
}ArcNode;

typedef struct VNode{//顶点表结点
   VertextType data;//顶点信息
   ArcNode *first;//指向第一条依附该顶点弧的指针
}VNode,AdjList[MaxVertexNum];

typedef struct{
   AdjList vertices;//邻接表
   int vexnum ,arcnum;//图的顶点数和弧数
}ALGraph;//ALGraph 是以邻接表存储的图类型

图的邻接存储方式具有以下特点：

①如果G是无向表，则所需的存储空间为O(|v|+2|E|);如果G是有向图，则所需的存储空间为O(|V|+|E|)。前者的倍数2是由于无向图中，每条边在邻接表中出现了两次。

②对于稀疏图，采用邻接表表示将极大地节省存储空间。

③优点：在邻接表中，给定一顶点，能很容易地找出它的所有邻边，因为只需要读取它的邻接表就可以了。在邻接矩阵中，相同的操作则需要扫描一行，花费的时间为O(n)。

缺点：但是要确定给定的两个顶点间是否存在边，则在邻接矩阵里就可以立刻查到，在邻接表中则需要在相应结点对应的边表中查找另一结点，效率较低。

④在有向图的邻接表表示中，求一个给定顶点的出度只需计算其邻接表中的结点个数即可；但求其顶点的入度，则需要遍历全部的邻接表。因此，也有人采用逆邻接表的存储方式来加速求解给定顶点的入度。当然，这实际上与邻接表存储方式是类似的。

⑤图的邻接表表示并不唯一，这是因为在每个顶点对应的单链表中，各边结点的链接次序可以是任意的，取决于建立邻接表的算法以及边的输入次序。