邻接表

图有两种主要的存储结构，它们是邻接矩阵表示法和邻接表表示法。邻接表是图的一种链式存储结构，在邻接表中，对图中每个顶点建立一个单链表，n个顶点，就要建n个链表。第i个单链表中的结点表示依赖于顶点vi的边。单链表中每一个结点称为表结点，应包括三个域邻接点域、链域和数据域。邻接点域，用以存放与vi相邻接的顶点序号；链域用以指向与vi邻接的下一个结点,数据域存储和边或弧有关的的信息。

另外，每一个单链表附设一个表头结点。每一个表头结点有两个域数据域和链域，数据域用来存放顶点vi的名或其它有关的信息；链域用来指向vi的邻接表中的第一个结点(见图5-7)。为了便于管理和随机访问任一顶点的单链表，将所有单链表的头结点通常以顺序结构的形式存储，一般定义成一维数组。