上节讲到，邻接矩阵对于存储稠密图比较有效，而不适合存储稀疏图 在这里介绍另一种较好的解决方法——邻接表
链表：用于存放边的信息 数组：用于存放顶点的信息
对于每个顶点分别建立一个线性链表，即对n个顶点来说，邻接表由n个线性链表组成。
把图中所出现的所有点都放入这个数组中，用它们在该数组的下标表示在图的位置。
每个链表前面设置一个头结点，称之为顶点结点。 设两个域，顶点(vertex)域用于存档顶点数据信息，指针域(link域)用于指出依附于该顶点的第一条边所对应的链结点的地址。 为了方便地访问任意顶点的链表，我们将以顺序存储结构（数组）形式存储的顶点在图中的位置，用它在数组中的下标表示
每个链表中的链结点称为边结点，它表示依附于某个顶点的一条边。 对于顶点i 的这一条链表 设三个域，邻接点（adjvex）域用于存放该边的另一端的顶点j（邻接点）在顶点数组中的位置，权（weight）域用于存放一条边的权值，若图不是网络，则无此域，指针域（next 域）用于指出与顶点i邻接的其他的边所对应的边结点的位置，即通过next域将表示了与顶点i连接的所有边的边结点都连起来，构成线性链表，最后一个边结点的指针域存NULL
typedef struct edge{ int adjvex; //该边的邻接点在顶点数组中的下标 int weight; //该边权值 struct edge *next; //指向下一个边结点 }Elink; typedef struct ver{ vertpye vertex; //vertpye：顶点的数据信息的类型， vertex：顶点的数据信息 Elink *link; //指向第一条边所对应的边结点 }Vlink;1.无向图，若n个顶点，e条边，则其邻接表需要n个顶点结点，2e个边结点。 2.在总的边数小于n(n-1)/4的情况下，邻接表比邻接矩阵省空间 3.无向图中，第i个链表中的边结点数目等于第i个顶点的度 有向图中，第i个链表中的边结点数目等于第i个顶点的出度，但是求入度比较麻烦，需要扫描邻接表，为此，可以建立逆邻接表结构 4.无向图的邻接表中的边结点数目必为偶数，因此若边结点数目为奇数，则必为有向图。 5.邻接表要找到任意顶点的邻接点比较容易，但是要确定任意两个顶点之间的关系，需要遍历。 6.对一个图，其邻接表与逆邻接表不唯一
输入：带权有向图的n个顶点和e个表示边的顶点偶对
void ADJLIST(VLink G[], int n, int e){ int k, vi, vj, weight; Elink *p,*q; for(k = 0; k < n; k++){ G[k].vertex = k + 1; G[k].link = NULL; //建立n个顶点结点 } for(k = 0;k < e;k ++){ scanf("%d %d %d",&vi, &vj, &weight); p=(Elink*)malloc(sizeof(Elink)); p->adjvex = vj - 1; p->weight=weight; p->next=NULL; if(!G[vi-1].link) G[vi-1].link=p else{ q=G[vi-1].link; while(q->next) q=q->next; q->next-p;//找到表尾后插入 } } }若输入顶点信息为顶点编号，则时间复杂度为O（n+e） 否则，需要查找才能得到顶点在图中的位置信息，复杂度为O（n*e）
