图的邻接表表示法 图的邻接表表示法类似于树的孩子链表表示法。对于图G中的每个顶点vi，该方法把所有邻接于vi的顶点vj链成一个带头结点的单链表，这个单链表就称为顶点vi的邻接表(Adjacency List)。 1． 邻接表的结点结构 （1）表结点结构 ┌────┬───┐ │adjvex │next │ └────┴───┘ 邻接表中每个表结点均有两个域: ① 邻接点域adjvex 存放与vi相邻接的顶点vj的序号j。 ② 链域next 将邻接表的所有表结点链在一起。 注意： 若要表示边上的信息(如权值)，则在表结点中还应增加一个数据域。 （2）头结点结构 ┌────┬─────┐ │vertex │firstedge │ └────┴─────┘ 顶点vi邻接表的头结点包含两个域： ① 顶点域vertex 存放顶点vi的信息 ② 指针域firstedge vi的邻接表的头指针。 注意： ① 为了便于随机访问任一顶点的邻接表，将所有头结点顺序存储在一个向量中就构成了图的邻接表表示。 ② 有时希望增加对图的顶点数及边数等属性的描述，可将邻接表和这些属性放在一起来描述图的存储结构。 2．无向图的邻接表 对于无向图，vi的邻接表中每个表结点都对应于与vi相关联的一条边。因此，将邻接表的表头向量称为顶点表。将无向图的邻接表称为边表。 注意： n个顶点e条边的有向图，它的接表表示中有n个顶点表结点和e个边表结点。 5．邻接表的形式说明及其建表算法 （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的出边表头部即可。 ② 建立网络的邻接表时，需在边表的每个结点中增加一个存储边上权的数据域。
注：转帖，非原创
