邻接表是图的另一种存储结构（使用链表的思想）。
该方式的基本思路：顶点表后指向邻接表，邻接表中依次为当前顶点的邻接点
准备工作
与邻接矩阵类似，在构造邻接表之前，需要存储各个顶点的信息，在这里使用结构体存储。因此，在构造邻接表之前，需要先定义两个结构体：邻接表结构体、顶点结构体。【其中，都需要用到指向邻接表的指针！】
struct EdgeNode{ //邻接表 int ad; //记录邻接点的位置 EdgeNode *next; //指向邻接表的指针
};
struct VertxNode{ //顶点表 char vertx;EdgeNode *firstEdge;//指向邻接表的指针
};
类的声明
与邻接矩阵类似，在这里，继续使用C++面向对象的方法完成构建。
class AlGraph{
public:AlGraph(char a[],int n,int e); //通过顶点数据、点数、边数建邻接表 ~AlGraph(); //使用链表存储，非静态存储，需析构！void dfs(int v); void bfs(int v);
private:VertxNode adjlist[MaxSize]; //结构数组存放各顶点 int vertxNum,edgeNum; //点数、边数 };
建表
构造函数
构造函数与单链表的头插法类似，但又不完全相同。如图，单链表中的first结点为一个结构体变量，其中包含next指针。
在实现单链表的头插法时，首先将插入元素的next指针与first指针指向同一位置，之后将头指针的next指针指向新插入的元素。而在邻接表构建中，顶点结构体就相当于单链表头插构造中的整个first结点，顶点结构体中的firstEdge指针就相当于单链表first结点的next指针！（如图所示）
邻接表的构造过程用以下代码实现：
AlGraph::AlGraph(char a[],int n,int e){vertxNum=n,edgeNum=e;int i,j,k;//顶点结构初始化（抄入顶点数据并将头指全部置空） for(i=0;i<vertxNum;i++){adjlist[i].vertx=a[i];adjlist[i].firstEdge=NULL;} //使用链表头插法，对输入的边关系挂链 EdgeNode *s=NULL;for(k=0;k<edgeNum;k++){cout << "输入边的两个顶点编号：";cin>>i>>j; //输入顶点，i已存入顶点结构，j存入邻接点域。s=new EdgeNode;s->ad=j; //将j挂链到i上 (头插)s->next=adjlist[i].firstEdge;adjlist[i].firstEdge=s;}
}
析构函数
由于邻接表使用链表存储数据，为动态存储，不同于邻接矩阵的数组存储结构。因此，需要手动写析构函数！
析构过程的思路及代码如下：
AlGraph::~AlGraph(){//使用链表存储邻接点，存储结构非静态，需循环删除指针EdgeNode *p,*q; //工作指针p ，临时指针q（暂存被删除元素） p=NULL,q=NULL;for(int i=0;i<vertxNum;i++){p=q=adjlist[i].firstEdge;while(p){p=p->next;delete q; //删除临时指针指向的数据 q=p; //更新临时指针指向 }}
}
图的遍历
与邻接矩阵相同，有两种方式对图进行遍历：DFS、BFS。其思路与邻接矩阵时实现的思路完全一样，所不同的仅仅是对链表的遍历过程。
DFS
void AlGraph::dfs(int v){cout<<adjlist[v].vertx; vis[v]=1;//遍历邻接表EdgeNode *p=NULL;p=adjlist[v].firstEdge; //工作指针初始化为邻接表第一个元素 int i; while(p){i=p->ad;if(!vis[i]) dfs(i); p=p->next;}
}
BFS
void AlGraph::bfs(int v){//思路：用队列，将元素访问、标记、入队 int front,rear;front=rear=-1;int Q[MaxSize],j,t; //t存储出队元素，j存储邻接点位置 cout<<adjlist[v].vertx;vis[v]=1;Q[++rear]=v;//从起点出发遍历邻接表 EdgeNode *p=NULL; while(front!=rear){t=Q[++front];p=adjlist[t].firstEdge; //工作指针指向顶点后第一个邻接点while(p){j=p->ad;if(!vis[j]){cout<<adjlist[j].vertx;vis[j]=1;Q[++rear]=j;}p=p->next;} }
}
完整代码
如图，测试边为:(0 1)(0 3)(0 4)(1 2)(2 4)(3 2)(3 4)
#include<iostream>
using namespace std;
const int MaxSize=10;
int vis[MaxSize]={0};
struct EdgeNode{ //邻接表 int ad; //记录邻接点位置 EdgeNode *next;
};
struct VertxNode{ //顶点表 char vertx;EdgeNode *firstEdge;//顶点表指向邻接表，指针为邻接表类型
};
//思路：顶点表后指向邻接表，邻接表中依次为当前顶点的邻接点
class AlGraph{
public:AlGraph(char a[],int n,int e); //通过顶点数据、点数、边数建邻接表 ~AlGraph(); //使用链表存储，非静态存储，需析构！void dfs(int v); void bfs(int v);
private:VertxNode adjlist[MaxSize]; //结构数组存放各顶点 int vertxNum,edgeNum; //点数、边数 };
AlGraph::AlGraph(char a[],int n,int e){vertxNum=n,edgeNum=e;int i,j,k;//顶点结构初始化（抄入顶点数据并将头指全部置空） for(i=0;i<vertxNum;i++){adjlist[i].vertx=a[i];adjlist[i].firstEdge=NULL;} //使用链表头插法，对输入的边关系挂链 EdgeNode *s=NULL;for(k=0;k<edgeNum;k++){cout << "输入边的两个顶点编号：";cin>>i>>j; //输入顶点，i已存入顶点结构，j存入邻接点域。s=new EdgeNode;s->ad=j; //将j挂链到i上 (头插)s->next=adjlist[i].firstEdge;adjlist[i].firstEdge=s;}
} void AlGraph::dfs(int v){cout<<adjlist[v].vertx; vis[v]=1;//遍历邻接表EdgeNode *p=NULL;p=adjlist[v].firstEdge; //工作指针初始化为邻接表第一个元素 int i; while(p){i=p->ad;if(!vis[i]) dfs(i); p=p->next;}
}void AlGraph::bfs(int v){//思路：用队列，将元素访问、标记、入队 int front,rear;front=rear=-1;int Q[MaxSize],j,t; //t存储出队元素，j存储邻接点位置 cout<<adjlist[v].vertx;vis[v]=1;Q[++rear]=v;//从起点出发遍历邻接表 EdgeNode *p=NULL; while(front!=rear){t=Q[++front];p=adjlist[t].firstEdge; //工作指针指向顶点后第一个邻接点while(p){j=p->ad;if(!vis[j]){cout<<adjlist[j].vertx;vis[j]=1;Q[++rear]=j;}p=p->next;} }
}AlGraph::~AlGraph(){//使用链表存储邻接点，存储结构非静态，需循环删除指针EdgeNode *p,*q; //工作指针p ，临时指针q（暂存被删除元素） p=NULL,q=NULL;for(int i=0;i<vertxNum;i++){p=q=adjlist[i].firstEdge;while(p){p=p->next;delete q; //删除临时指针指向的数据 q=p; //更新临时指针指向 }}
} int main( )
{char ch[ ] = {'A','B','C','D','E'};int i;AlGraph ALG(ch, 5, 7); //建立具有5个顶点6条边的有向图for (i = 0; i < MaxSize; i++)vis[i] = 0;cout << "深度优先遍历序列是：";ALG.dfs(0); //从顶点0出发进行深度优先遍历cout<<endl;for (i = 0; i < MaxSize; i++)vis[i] = 0;cout << "广度优先遍历序列是："; ALG.bfs(0); //从顶点0出发进行广度优先遍历return 0;
}
