邻接表的定义和存储以及有向图无向图的邻接存储

邻接表

邻接表(Adjacency List)是图的一利链式存储结构。

因为，图是有顶点和边构成，所以，其存储结点也有下面两种：

• 头结点（顶点形成的结点）

• 表结点（边形成的结点）

• 头结点

P->data: 存放顶点的信息;

P->firstarc:存放与该顶点相关联的第一条边结点地址

• 边结点

P->adjvex: 与该顶点相邻接的顶点的下标

P->infor: 存放该条边的信息;

P->nextarc:存放与该顶点相关联的下一条边的结点地址;

邻接表定义

对于含有 n 个顶点的图可以用 n 个带头结点的单链表存储。其中第 i 个单链表是以图中顶点 vi 为头头结点，是以与顶点 vi 相关联的边结点为数据结点而构成的。表头结点通常以顺序存储结构的形式，以便可随机访问任一顶点的链表。

图的邻接表存储表示

#define MAX VERTEX NUM 20

typedef struct ArcNode{ (弧结点的结构)

int adjvex;(该弧所指向的顶点的位置)

struct ArcNode *nextarc;(指向下一条弧的指针)

InfoType *info; (该弧相关信息的指针)

}ArcNode;

typedef struct VNode{ (顶点结构)

VertexType data;(顶点信息)

ArcNode *firstarc;(指向第一条依附该顶点的弧的指针)

}Vnode，AdjList[MAX_VERTEX_NUM ];

typedef struct {

AdjList verticds;

int vexnum, arcnum;(顶点数与弧数)

int kind; (图的种类标志)

}ALGraph;

无向图的邻接表存储

注意:无向图的邻接表存储中，每条边都存储两次。所以，对于含有 N 个顶点，E 条边的无向图，若每个顶点与每条边都占用一个存储单元，那么，它共占用 N+2*E 个存储单元。

有向图的邻接表存储

由邻接表中很容易求出每个顶点的出度。但要求入度必须遍历所有表结点的邻接顶点域。但在逆邻接表中求入度很方便(见下图)。

有向图的逆邻接表

逆邻接表是以顶点为头部顶点的边所组成的。每个单链表中边结点的个数为该顶点的入度。