邻接表就是图的一种链式结构。对图中的每一个顶点Vi建立以个单链表来存放。邻接表中的每个单链表的第一个结点存放顶点的信息，并把这个结点看作链表的表头，其余结点存放与结点相关的信息。由此可知：邻接表有两张表组成，一张是表头结点表也即是存放顶点和其信息的表，还有一张是边表，边表用于存放边。
表头结点表：有数据域和链域两部分。数据与存放顶点的名称或其他信息。
边表：有数据域、链域和邻接点域。邻接点域用于存放与Vi邻接的顶点的位置。数据与存放边相关信息例如权值。链域指示Vi邻接的下一条边的结点
一般来说为了方便 顶点表设置为一个结构体数组。
邻接表的优点：，也就是说要用两张表才能计算出来。相对临界矩阵来说，邻接矩阵的空间效率为O(n的平方)所以邻接表比较节省空间
邻接表的缺点：使用于稀疏图。在用于无向图中其空间效率为O(n+2e)，并且可以计算出图中结点的度。而用在有向图中，其空间效率为O(n+e),但是只能计算出度，如果真要计算入度就要用到逆邻接表了
此处给出无向图邻接表的实现代码：（编写工具 visual studio 2015）
#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"#define MaxInt 323767 //表示极大值
#define MVNum 100 //表示最大的顶点数
#define OK 1;
#define FAILE 0;
typedef char VerTexType;
typedef int ArcType;
typedef struct arcNode {
int adjvex;//指向哪一个定点
arcNode *nextarc;
int data; //权值
}ArcNode;
typedef struct VNode {
int data;
arcNode *firstarc;
}VNode,adjList[MVNum];
typedef struct Graph {
adjList verList;
int vexnum, arcnum;
}ALGraph;
int Locatevex(ALGraph g,int vex) {
int i;
for (i = 0; i < g.vexnum;i++) {
if (g.verList[i + 1].data == vex) {
return (i+1);
}
}
return FAILE;
}
void init(ALGraph &g) {//初始化图，并存放在链表当中
int i;int k;
printf("请输入顶点数 和 边总数\n");
scanf_s("%d %d", &g.vexnum, &g.arcnum);
printf("-----------------------------\n");
printf("初始化顶点数和总变数成功\n");
printf("-----------------------------\n");
for (i = 0; i < g.vexnum; i++) {
scanf_s("%d", &g.verList[i+1].data);
g.verList[i + 1].firstarc = NULL;
printf("正在初始化 %d 个顶点:%d \n",(i + 1),g.verList[i+1].data);
}
printf("-----------------------------\n");
printf("初始化顶点数据成功\n");
printf("-----------------------------\n");
for (k = 0;k < g.arcnum; k++) {
int v1, v2;
printf("--------------------------------------------------------------------\n");
printf("请输入顶点1 和 顶点2 \t 温馨提示：顶点1和顶点2是为输入改变所依附的点\n");
printf("--------------------------------------------------------------------\n");
scanf_s("%d %d", &v1,&v2);
v1 = Locatevex(g,v1);
v2 = Locatevex(g, v2);
ArcNode *p1 = new ArcNode;
p1->adjvex = v2;
p1->nextarc = g.verList[v2].firstarc;
g.verList[v1].firstarc = p1;
ArcNode *p2 = new ArcNode;
p2->adjvex = v1;
p2->nextarc = g.verList[v1].firstarc;
g.verList[v2].firstarc = p2;
}
printf("-----------------------------\n");
printf("初始化边成功\n");
printf("-----------------------------\n");
}
void show(){
}
int main()
{
ALGraph g;
init(g);
return 0;
}
运行效果：
