附录D　邻接表

邻接表是图的一种最主要存储结构，用来描述图上的每一个点。对图的每个顶点建立一个容器（n个顶点建立n个容器），第i个容器中的结点包含顶点vi的所有邻接顶点。

例如，有向图如图D-1所示，其邻接表如图D-2所示。

图D-1　有向图G

图D-2　邻接表

1．数据结构

邻接表用到两个数据结构：

（1）一个是头结点表，用一维数组存储。包括顶点和指向第一个邻接点的指针。

（2）一个是每个顶点vi的所有邻接点构成一个线性表，用单链表存储。无向图称为顶点vi的边表，有向图称为顶点vi作为弧尾的出边表，存储的是顶点的序号，和指向下一个边的指针。

头结点：

struct Hnode{ //定义顶点类型Node *first; //指向第一个邻接点
};

首先创建邻接表表头，初始化每个结点的第一个邻接点first为NULL，如图D-3所示。