在邻接表表示中有两种结点结构,如下图所示 顶点域边表头指针 邻接点域指针域 vertex firstedge adnex next 顶点表 边表 邻接矩阵表示的结点结构 一种是顶点表的结点结构,它由顶点域( vertex)和指向 第一条邻接边的指针域( firstedge)构成,另一种是边表( 即邻接表)结点,它由邻接点域( adjvex)和指向下一条邻接 边的指针域(nex构成。对于网图的边表需再增设一个存储 边上信息(如权值等)的域(info),网图的边表结构如下 图所示。 邻接点域边上信息指针域 adivex info next 网图的边表结构 2021年1月21日 数据结构讲义 21
2021年1月21日 数据结构讲义 21 • 在邻接表表示中有两种结点结构，如下图所示。 一种是顶点表的结点结构，它由顶点域（vertex）和指向 第一条邻接边的指针域（firstedge）构成，另一种是边表（ 即邻接表）结点，它由邻接点域(adjvex)和指向下一条邻接 边的指针域(next)构成。对于网图的边表需再增设一个存储 边上信息（如权值等）的域（info），网图的边表结构如下 图所示
下图给出无向图及对应的邻接表表示。 yO V3 V1V2 序号 vertex fistedge Ⅵ仍 3∧ A 0--1∧ 图的邻接表表示 2021年1月21日 数据结构讲义 22
2021年1月21日 数据结构讲义 22 • 下图给出无向图及对应的邻接表表示
邻接表表示的形式描述如下: # define max VerNum100/年最大顶点数为100*/ p typedef struct node *边表结点* Int adver, /*邻接点域* struct node x next *指向下一个邻接点的指针域* /若要表示边上信息,则应增加一个数据域ifo* J Edge node pede struct vnode 顶点表结点*/ Vertexlype vertex /*顶点域* EdgeNode* firstedge;/边表头指针* 3 VertexNode typedef Vertex Node Adjlist/ Max VertexNum\2.光型 /* AdjListy是邻接表类 ty pede struct Adjlist adjlist *邻接表* Int ne /*顶点数和边数* JALGraph; /体 ALGraph是以邻接表方式存储的图类型* 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 23 邻接表表示的形式描述如下： ＃define MaxVerNum 100 /*最大顶点数为100*/ typedef struct node{ /*边表结点*/ int adjvex; /*邻接点域*/ struct node * next; /*指向下一个邻接点的指针域*/ /*若要表示边上信息，则应增加一个数据域info*/ }EdgeNode; typedef struct vnode{ /*顶点表结点*/ VertexType vertex; /*顶点域*/ EdgeNode * firstedge; /*边表头指针*/ }VertexNode; typedef VertexNode AdjList[MaxVertexNum]; /*AdjList是邻接表类型*/ typedef struct{ AdjList adjlist; /*邻接表*/ int n,e; /*顶点数和边数*/ }ALGraph; /*ALGraph是以邻接表方式存储的图类型*/
建立一个有向图的邻接表存储的算法如下: a void CreateALGraph(ALGraph*G) *建立有向图的邻接表存储* EdgeNode *S, printf"请输入顶点数和边数(输入格式为顶点数边数:n"); scanf("d,9%d",&(G->n),&(G->e);读入顶点数和边数* printf("请输入顶点信息(输入格式为顶点号CR>)m") for(=0;1<G>ni+) *建立有n个顶点的顶点表*/ scant("n%oc",&(G> adjlist[]. vertex),/读入顶点信息* G-> adjlist[ 1]. firstedge=NULL;*顶点的边表头指针设为空 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 24 • 建立一个有向图的邻接表存储的算法如下： void CreateALGraph(ALGraph *G) /*建立有向图的邻接表存储*/ { int i,j,k; EdgeNode * s; printf("请输入顶点数和边数(输入格式为:顶点数,边数)：\n"); scanf("%d,%d",&(G->n),&(G->e)); /*读入顶点数和边数*/ printf("请输入顶点信息(输入格式为:顶点号<CR>)：\n"); for (i=0;i<G->n;i++) /*建立有n个顶点的顶点表*/ { scanf("\n%c",&(G->adjlist[i].vertex)); /*读入顶点信息*/ G->adjlist[i].firstedge=NULL; /*顶点的边表头指针设为空*/ }
printf("请输入边的信息(输入格式为j):mn"); for(k=0; k<G->e k++) /*建立边表* i scanf("n%od, %d", &i, &j); /读入边<VV>的顶点对应序号* S-(EdgeNode*)malloc(sizeof(Edge Node)) 生成新边表结点s* S->adjvex-J *邻接点序号为许 S->next=G->adjlist[1]. firstedge; /*将新边表结点s插入到顶点Ⅴ的边表头部* G->adjlist[]. firstedge 2021年1月21日 数据结构讲义
2021年1月21日 数据结构讲义 25 printf("请输入边的信息(输入格式为:i,j)：\n"); for (k=0;k<G->e;k++) /*建立边表*/ { scanf("\n%d,%d",&i,&j); /*读入边<Vi,Vj>的顶点对应序号*/ s=(EdgeNode*)malloc(sizeof(EdgeNode)); /*生成新边表结点s*/ s->adjvex=j; /*邻接点序号为j*/ s->next=G->adjlist[i].firstedge; /*将新边表结点s插入到顶点Vi的边表头部*/ G->adjlist[i].firstedge=s; } }