一、邻接表

二、图的邻接表表示法(1．有向图的邻接表 2．有向图的逆邻接表)

一、邻接表

邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表（n个顶点建立n个单链表），第i个单链表中的结点包含顶点Vi的所有邻接顶点。又称链接表。

补充：

1.在有向图的邻接表中不易找到指向该顶点的弧。

2.在有向图的邻接表中，对每个顶点，链接的是以该顶点为弧尾的邻接点。

二、图的邻接表表示法

注意：

n个顶点e条边的无向图的邻接表表示中有n个顶点表结点和2e个边表结点。

1．有向图的邻接表

对于有向图，vi的邻接表中每个表结点都对应于以vi为始点射出的一条边。因此，将有向图的邻接表称为出边表。

【例】有向图G6的邻接表表示如下图所示，其中顶点v1的邻接表上两个表结点中的顶点序号分别为0和4，它们分别表示从v1射出的两条边(简称为v1的出边)：<v1，v0>和<v1，v4>。

注意：

n个顶点e条边的有向图，它的邻接表表示中有n个顶点表结点和e个边表结点。

2．有向图的逆邻接表

在有向图中，为图中每个顶点vi建立一个入边表的方法称逆邻接表表示法。

入边表中的每个表结点均对应一条以vi为终点(即射入vi)的边。

【例】G6的逆邻表如上面(b)图所示，其中v0的人边表上两个表结点1和3分别表示射人v0的两条边(简称为v0的入边)：<v1，v0>和<v3，v0>。

注意：

n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。

3．邻接表的形式说明及其建表算法

（1）邻接表的形式说明

typedef struct node{//边表结点

int adjvex； //邻接点域

struct node *next； //链域

//若要表示边上的权，则应增加一个数据域

}EdgeNode;

typedef struct vnode{ //顶点表结点

VertexType vertex； //顶点域

EdgeNode *firstedge；//边表头指针

}VertexNode；

typedef VertexNode AdjList[MaxVertexNum]；//AdjList是邻接表类型

typedef struct{

AdjList adjlist；//邻接表

int n，e； 图中当前顶点数和边数

}ALGraph； //对于简单的应用，无须定义此类型，可直接使用AdjList类型。

(2)建立无向图的邻接表算法

void CreateALGraPh(ALGrahp *G)

{//建立无向图的邻接表表示

int i，j，k；

EdgeNode *s；

scanf("%d%d"，&G->n，&G->e)； //读人顶点数和边数

for(i=0；i<G->n；i++){//建立顶点表

G->adjlist[i].vertex=getchar()； //读入顶点信息

G->adjlist[i].firstedge=NULL；//边表置为空表

}

for(k=0；k<G->e；k++){//建立边表

scanf("%d%d"，&i,&j)；读入边(vi，vj)的顶点对序号

s=(EdgeNode *)malloc(sizeof(EdgeNode))； //生成边表结点

s->adjvex=j; //邻接点序号为j

s->next=G->adjlist[i].firstedge；

G->adjlist[i].firstedge=s； //将新结点*s插入顶点vi的边表头部

s=(EdgeNode *)malloc(sizeof(EdgeNode))；

s->adjvex=i; //邻接点序号为i

s->next=G->adjlist[j].firstedge；

G->adjlistk[j].firstedge=s； //将新结点*s插入顶点vj的边表头部

}//end for

}CreateALGraph

该算法的时间复杂度是O(n+e)。

注意：

① 建立有向图的邻接表更简单，每当读入一个顶点对序号<i,j>时，仅需生成一个邻接序号为j的边表结点，将其插入到vj的出边表头部即可。

② 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。