邻接表：所谓邻接表（adjacency list），就是把从同一个顶点发出的边链接在同一个称为边链表的单链表中。边链表的每个结点代表一条边，称为边结点。每个边结点有2 个域：该边终点的序号，以及指向下一个边结点的指针。在邻接表中，还需要一个用于存储顶点信息的顶点数组。例如，图1.19(a)所示的有向图对应的邻接表如图(b)所示。在顶点数组中，每个元素有两个成员：一个成员用来存储顶点信息；另一个成员为该顶点的边链表的表头指针，指向该顶点的边链表。如果没有从某个顶点发出的边，则该顶点没有边链表，因此表头指针为空，如图1.19(b)中的顶点G。在该图中，如果指针为空，则用符号“∧”表示。
图1.19有向图的邻接表
在邻接表每个顶点的边链表中，各边结点所表示的边都是从该顶点发出的边，因此这种邻接表也称为出边表。采用邻接表存储图时，求顶点的出度很方便，只需要统计每个顶点的边链表中边结点的个数即可，但在求顶点的入度时就比较麻烦。在图1.19(b)中，顶点B 的边链表有3 个边结点，分别表示边<B, F>、<B, E>和<B, C>，因此顶点B 的出度为3；顶点C 的边链表中只有1 个边结点，表示边<C, E>，因此顶点C 的出度为1。如果需要统计各顶点的入度，可以采用逆邻接表存储表示图。所谓逆邻接表，也称为入边表，就是把进入同一个顶点的边链接在同一个边链表中。
图1.20有向图的逆邻接表
例如，图1.20(a)所示的有向图对应的逆邻接表如图(b)所示。在图1.20(b)中，顶点B 的边链表有2 个边结点，分别表示边<E, B>和<A, B>，因此顶点B 的入度为2；顶点C 的边链表中也有2个边结点，分别表示边<D, C>和<B, C>，因此顶点C 的入度也为2。
接下来以有向图为例介绍邻接表的实现方法。为了方便求解顶点的出度和入度，在实现时，把出边表和入边表同时包含在图的邻接表结构中。有向图的邻接表用一个结构体LGraph 存储表示，其中包含3 个成员：顶点数组vertexs，顶点数vexnum 和边的数目arcnum，其中顶点数组vertexs 中每个元素都是VNode 结构体变量。VNode 结构体变量存储图中每个顶点，它包含3 个成员：顶点信息、出边表的表头指针和入边表的表头指针，其中后面两个成员都是ArcNode 结构体类型的指针。ArcNode 结构体存储边链表中的边结点，它包含2 个成员：边的另一个邻接点的序号，以及指向下一个边结点的指针。
例题：
问题描述：用邻接表存储有向图，并输出各顶点的出度和入度。
输入描述：输入文件中包含多个测试数据，每个测试数据描述了一个无权有向图。每个测试数据的第一行为两个正整数n 和m，1≤ n ≤ 100，1≤ m ≤ 500，分别表示该有向图的顶点数目和边数，顶点的序号从1 开始计起。接下来有m 行，每行为两个正整数，用空格隔开，分别表示一条边的起点和终点。每条边出现一次且仅一次，图中不存在自身环和重边。输入文件最后一行为0 0，表示输入数据结束。
输出描述：
对输入文件中的每个有向图，输出两行：第1 行为n 个正整数，表示每个顶点的出度；第2行也为n 个正整数，表示每个顶点的入度。每两个正整数之间用一个空格隔开，每行的最后一个正整数之后没有空格。
样例输入：
4 7
1 4
2 1
2 2
2 3
2 3
4 2
4 3
0 0
样例输出：
1 4 0 2
1 2 3 1
代码实现：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#define INF 99999999
using namespace std;
const int maxn=105;
struct ArcNode{//边结点
int adjvex;//有向边的另一个邻接点的序号
ArcNode *nextarc;//指向下一个边结点的指针
};
struct VNode{//顶点
int data;//顶点信息
ArcNode *head1;//出边表的表头指针
ArcNode *head2;//入边表的表头指针
};
struct LGraph{//图的邻接表存储结构
VNode vertexs[maxn];//顶点数组
int vexnum,arcnum;//顶点数和边数
}LG;
void CreateLG(){
ArcNode *p;//用来构造边链表的边结点指针
int v1,v2;
//LG.vexnum=LG.arcnum=0;
//scanf("%d %d",&LG.vexnum,&LG.arcnum);
for(int i=0;i<LG.vexnum;i++){//初始化表头指针为空
LG.vertexs[i].head1=LG.vertexs[i].head2=NULL;
}
for(int i=0;i<LG.arcnum;i++){
scanf("%d %d",&v1,&v2);
v1--,v2--;
p = new ArcNode;//假定有足够空间
p->adjvex = v2;
p->nextarc = LG.vertexs[v1].head1;//插入链表
LG.vertexs[v1].head1=p;
p = new ArcNode;
p->adjvex = v1;
p->nextarc = LG.vertexs[v2].head2;
LG.vertexs[v2].head2=p;
}
}
void DeleteLG(){
ArcNode *p;//用来指向边链表中各边结点的指针
for(int i=0;i<LG.vexnum;i++){
p=LG.vertexs[i].head1;//释放第i个顶点出边表各边节点所占的存储空间
while(p!=NULL){
LG.vertexs[i].head1=p->nextarc;
delete p;
p=LG.vertexs[i].head1;
}
p=LG.vertexs[i].head2;//释放第i个顶点入边表各边节点所占的存储空间
while(p!=NULL){
LG.vertexs[i].head2=p->nextarc;
delete p;
p=LG.vertexs[i].head2;
}
}
}
int main()
{
int id,od;//顶点的入度跟出度
ArcNode *p;//用来遍历边链表的边结点指针
while(scanf("%d %d",&LG.vexnum,&LG.arcnum)){
if(LG.arcnum+LG.vexnum==0)
break;
CreateLG();
for(int i=0;i<LG.vexnum;i++){//统计各顶点出度并输出
od=0;
p=LG.vertexs[i].head1;
while(p!=NULL){
od++;
p=p->nextarc;
}
if(i==0) printf("%d",od)
;
else printf(" %d",od);
}
printf("
");
for(int i=0;i<LG.vexnum;i++){//统计各顶点入度并输出
id=0;
p=LG.vertexs[i].head2;
while(p!=NULL){
id++;
p=p->nextarc;
}
if(i==0) printf("%d",id);
else printf(" %d",id);
}
printf("
");
DeleteLG();//释放
}
return 0;
}
邻接表的简单实现：
typedef struct
{
int to;
int w;
int next;
}Edge;
Edge e[MAX];
int pre[MAX];
//初始化
memset(pre,-1,sizeof(pre));
//输入
scanf("%d %d %d",&from,&to,&w1);
e[i].to = to;
e[i].w = w1;
e[i].next = pre[from];
pre[from] = i++;
上面这段代码中，边的结构体Edge由三个元素组成：弧头结点序号，边权值，下一条边的序号。e[i]指的是第i条边。pre[i]记录的是从当前输入的情况来看，序号为i的弧尾结点发出的第一条边的序号是pre[i]。