一、什么是邻接表

• 图的邻接表存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。
• 如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。表结点存放的是邻接顶点在数组中的索引。
• 对于无向图来说，使用邻接表进行存储也会出现数据冗余，表头结点A所指链表中存在一个指向C的表结点的同时，表头结点C所指链表也会存在一个指向A的表结点。

二、如何用邻接表建无向图

定义表头结点

typedef struct VNode {				//定义表头结点;ArcNode *fstArc;				//指向第一条依附于该表头的指针;string data;						//存放定点信息;
}AdVList;

定义边表节点

typedef struct ArcNode {			//定义边结点;int adv;						//该边所指向的顶点的位置;struct ArcNode *nextArc;		//指向下一条边的指针;int data;						//和该边相关的信息,存放权值的地方;
}ArcNode;

定义图

typedef struct ALGraph {			//邻接表;AdVList Vts[MNum];				//创建有MNum个结点的图;int Vrnum, arnum;				//图的定点数和边数;
};

创建无向图的邻接表

void CreateGraph(ALGraph &G)					//创建图的邻接表;
{string v1, v2;cout << "输入图的顶点数和边数：\n";cin >> G.Vrnum >> G.arnum;					//输入图的顶点数和边数;for (int i = 0; i < G.Vrnum; i++){cout << "输入第" << i + 1 << "个顶点的信息\n";cin >> G.Vts[i].data;					//输入顶点信息;G.Vts[i].fstArc = NULL;					//初始化依附顶点的第一条边的指针;}for (int i = 0; i < G.arnum; i++)			//根据每一条边来建图的邻接表;{cout << "输入第" << i + 1 << "条边的起点和终点\n";cin >> v1 >> v2;						//输入该边的两个顶点;int j, k;j = find(G, v1);						//找到v1在图中的位置;k = find(G, v2);						//找到v2在图中的位置;ArcNode *p1 = new ArcNode;				//新建一个边表结点*p1;ArcNode *p2 = new ArcNode;				//新建一个边表结点*p1;p1->adv = k;							//p1邻接点的序号为k;p1->nextArc = G.Vts[j].fstArc;			G.Vts[j].fstArc = p1;					//将新结点*p1插入顶点j的边表头部;p2->adv = j;							//p1邻接点的序号为j;p2->nextArc = G.Vts[k].fstArc;G.Vts[k].fstArc = p2;					//将新结点*p2插入顶点k的边表头部;}
}

三、遍历无向图邻接表

详见注释

顺序遍历邻接表

oid print(ALGraph &G)								//输出该图的邻接表;
{cout << "该图的邻接表为:\n";for (int i = 0; i < G.Vrnum; i++)				//遍历图的每个顶点表;{cout << G.Vts[i].data;						//先输出顶点;ArcNode *p = G.Vts[i].fstArc;				//将该顶点指向的下一条边赋给*p;while (p)									//遍历该顶点的所有边;{cout << " -> " << G.Vts[p->adv].data;p = p->nextArc;}cout << endl;}
}

深度优先遍历（DFS）

void DFS(ALGraph &G, int n)			//深度优先遍历该图;
{cout << G.Vts[n].data;			//先输出当前需要遍历的顶点的信息;vist[n] = false;				//把该顶点的标记修改;ArcNode* p = G.Vts[n].fstArc;while (p)						//遍历该顶点的所有边;{if (vist[p->adv]) {			//判断当前边的顶点的标记值是否被修改过;cout << " -> ";DFS(G, p->adv);			//没被修改过的话深度优先遍历该点;}p = p->nextArc;}
}

宽度优先遍历（BFS)

void BFS(ALGraph &G, int n)					//宽度优先遍历该图;
{queue<int> q;							//创建存放顶点位置的队列q;q.push(n);								//把第一个点放入队列;while (!q.empty())						//遍历队列q;{if (q.front() != 0) cout << " -> ";cout << G.Vts[q.front()].data;		//输出队首元素所在位置的顶点的信息;vist[q.front()] = true;				//修改已经输出过的顶点的标记值;ArcNode* p = G.Vts[q.front()].fstArc;while (p)							//遍历该顶点的所有边;{if (!vist[p->adv]) {			//判断该边指向的顶点有没有被遍历过;vist[p->adv] = true;		//如果没有被遍历过，修改该点的标记值;q.push(p->adv);				//把该点所在图中的位置信息放入队列;}p = p->nextArc;}q.pop();							//队首元素出队;}
}

四、完整代码

#include <iostream>
#include <string>
#include <cstring>
#include <queue>
#define MNum 103					//最大顶点数;using namespace std;
/*
5 6
A B C D E
A B
A D
B C
B E
E C
C D
*/
bool vist[MNum];					//顶点标记数组;typedef struct ArcNode {			//定义边结点;int adv;						//该边所指向的顶点的位置;struct ArcNode *nextArc;		//指向下一条边的指针;int data;						//和该边相关的信息,存放权值的地方;
}ArcNode;typedef struct VNode {				//定义表头结点;ArcNode *fstArc;				//指向第一条依附于该表头的指针;string data;						//存放定点信息;
}AdVList;typedef struct ALGraph {			//邻接表;AdVList Vts[MNum];				//创建有MNum个结点的图;int Vrnum, arnum;				//图的定点数和边数;
};int find(ALGraph &G, string x)		//寻找X在图中的位置的函数;
{for (int i = 0; i < G.Vrnum; i++)//遍历图的顶点，将所在位置的下标返回;{if (x == G.Vts[i].data)return i;}
}void CreateGraph(ALGraph &G)					//创建图的邻接表;
{string v1, v2;cout << "输入图的顶点数和边数：\n";cin >> G.Vrnum >> G.arnum;					//输入图的顶点数和边数;for (int i = 0; i < G.Vrnum; i++){cout << "输入第" << i + 1 << "个顶点的信息\n";cin >> G.Vts[i].data;					//输入顶点信息;G.Vts[i].fstArc = NULL;					//初始化依附顶点的第一条边的指针;}for (int i = 0; i < G.arnum; i++)			//根据每一条边来建图的邻接表;{cout << "输入第" << i + 1 << "条边的起点和终点\n";cin >> v1 >> v2;						//输入该边的两个顶点;int j, k;j = find(G, v1);						//找到v1在图中的位置;k = find(G, v2);						//找到v2在图中的位置;ArcNode *p1 = new ArcNode;				//新建一个边表结点*p1;ArcNode *p2 = new ArcNode;				//新建一个边表结点*p1;p1->adv = k;							//p1邻接点的序号为k;p1->nextArc = G.Vts[j].fstArc;			G.Vts[j].fstArc = p1;					//将新结点*p1插入顶点j的边表头部;p2->adv = j;							//p1邻接点的序号为j;p2->nextArc = G.Vts[k].fstArc;G.Vts[k].fstArc = p2;					//将新结点*p2插入顶点k的边表头部;}
}void print(ALGraph &G)								//输出该图的邻接表;
{cout << "该图的邻接表为:\n";for (int i = 0; i < G.Vrnum; i++)				//遍历图的每个顶点表;{cout << G.Vts[i].data;						//先输出顶点;ArcNode *p = G.Vts[i].fstArc;				//将该顶点指向的下一条边赋给*p;while (p)									//遍历该顶点的所有边;{cout << " -> " << G.Vts[p->adv].data;p = p->nextArc;}cout << endl;}
}void DFS(ALGraph &G, int n)			//深度优先遍历该图;
{cout << G.Vts[n].data;			//先输出当前需要遍历的顶点的信息;vist[n] = false;				//把该顶点的标记修改;ArcNode* p = G.Vts[n].fstArc;while (p)						//遍历该顶点的所有边;{if (vist[p->adv]) {			//判断当前边的顶点的标记值是否被修改过;cout << " -> ";DFS(G, p->adv);			//没被修改过的话深度优先遍历该点;}p = p->nextArc;}
}void BFS(ALGraph &G, int n)					//宽度优先遍历该图;
{queue<int> q;							//创建存放顶点位置的队列q;q.push(n);								//把第一个点放入队列;while (!q.empty())						//遍历队列q;{if (q.front() != 0) cout << " -> ";cout << G.Vts[q.front()].data;		//输出队首元素所在位置的顶点的信息;vist[q.front()] = true;				//修改已经输出过的顶点的标记值;ArcNode* p = G.Vts[q.front()].fstArc;while (p)							//遍历该顶点的所有边;{if (!vist[p->adv]) {			//判断该边指向的顶点有没有被遍历过;vist[p->adv] = true;		//如果没有被遍历过，修改该点的标记值;q.push(p->adv);				//把该点所在图中的位置信息放入队列;}p = p->nextArc;}q.pop();							//队首元素出队;}
}int main()
{ALGraph G;CreateGraph(G);						//创建图的邻接表;print(G);							//遍历图的邻接表;memset(vist, true, sizeof(vist));	//初始化标记数组;cout << "深度优先遍历该图为:";DFS(G, 0);							//深度优先遍历该图;cout << endl;cout << "宽度优先遍历该图为:";BFS(G, 0);							//宽度优先遍历该图;cout << endl;return 0;
}

蒟蒻一只，欢迎指正