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

邻接表

邻接表(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个存储单元。

有向图的邻接表存储

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

有向图的逆邻接表

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