使用邻接表的目的3:邻接矩阵是一种较好的存储结构，但在边数相对于顶点数较少的情况下，发现这种结构会给存储空间带来很大的浪费。 例如从3360图可以看出，除了arc[1][0]的权利值以外没有圆弧。 这些存储空间都浪费了。
邻接表有两个域，一个是顶点表域，一个是边表域，
定义邻接表结构类型:
//边表结构class arcnode { public : int adjvex； //存储某个顶点的邻接点信息，输入arcNode *next； //边表由一个个节点构成，像链表一样，需要next连接}； //顶点表字段classvertexnode { public : datatype vertex； //用于存储年龄、姓名等顶点信息的int weight； arcNode *firstedge； //每个顶点都有其相邻点，firstedeg指的是第一个相邻点}； 在有向图(网)的邻接表中存储图像(对于网图，有必要定义在边表节点中存储权重信息的info域) )。
定义图表类(定义顶点表就足够了。 接下来，创建一个节点，并在第一个表的firstedge字段中插入该节点。) )。
const int MaxSize=10； classmgraph { public : m graph (datatype a [ ]，int n，int e )； //构造函数创建具有n个节点、e条边的图voiddfstraverrse(intv )。 //深度优先导线测量贴图voidBFStraverse(intv )； //广度优先遍历图private : vertexnodeadjlist [ maxsize ]； //定义顶点表数组int vertexNum，arcNum； //定义顶点数和边数}；实现构造函数：
)决定图表的顶点数和边数，输入顶点信息并保存在顶点表中，对该顶点的边表保存的详细情况进行初始化。 1 .生成边连接的2个顶点I和j，2 .邻接点的编号为j，3的节点s。 在第I个边表的标头中插入s节点) )。
m graph :3360 m graph (datatype a [ ]，int n，int e ) {vertexNum=n； arcNum=e； int i，j； //输入顶点信息，初始化定点表for (I=0； ivertexNum； I ) {adjlist[i].vertex=a[i]； //将各顶点阵列信息代入对应的顶点adjlist[i].firstedge=NULL； //给各顶点的边表指针分配NULL，防止野指针} //如果定义有向图有一个a-b的边，则由于一个节点是b-a，所以有s和p两个节点. for(intk=0； karcNum； k({cinij； arcNode *s=new arcNode； //申请边表节点类型的内存，并将此节点连接到相应的头节点后面s-adjvex=j； //保存他的相邻点的是j s-next=adjlist[i].firstedge；//第I个边表的标头adjlist[i].firstedge=s； 因为用//头插入，所以侧标题指针是s arcNode *p=new arcNode； p-adjvex=i； p-next=adjlist[j].firstedge； adjlist[j].firstedge=p； }深度优先遍历(思路与相邻矩阵中的思路相同，可以检查我的相邻矩阵中的深度优先遍历。 但是，必须将以前的数组遍历作为链表遍历。 ）
//遍历时脑子里需要有图。 通过深度优先遍历，不依赖于图中各节点想怎么去//代码，而是头脑中没有图的画面卷入代码中voidmgraph 33603360 DFS traverse (intv ) /先访问数据. coutadjlllling visited[v]=1； arcNode *p=adjlist[v].firstedge； //发现相邻点，开始寻找该节点的相邻点while(p )=依次搜索=null(//顶点v的相邻点j ) /，判断该节点是否访问了j=p-adjvex； if(visited[j]==0) DFStraverse ) j； (}p=p-next； //边表中的这个节点访问该链中的下一个节点，}宽度优先遍历步骤：
1 .首先需要在外部定义队列，遇到顶点，首先访问，然后存放在队列中。 2 .如果队列不为空，则将队列的首元素移出队列以获取当前下标，3 .定义移动指针等于此下标的第一个指针字段，使用循环，然后移动该指针以查看该节点的所有邻居。 如果队列不为空，则内层环需要两个环来遍历此顶点的所有相邻点。 如果节点具有相邻节点，则确定是否已访问该相邻节点，如果未访问，则访问并排队。
//首先访问起始节点的元素将元素入队，然后如果队列不为空，则堆栈队列的起始元素，定义边表移动指针。 //如果此边表不为空，则判断是否访问了该节点，如果未访问，则访问并更改visited值，将访问的节点入队。 //如果已访问，则查看该节点的下一个节点是否已访问。 直到看完这个链条. voidmgraph :3360 bfs traverse (intv ) {front=rear=-1； coutadjlist[v].vertex； visited[v]=1； Q[ rear]=v； wile (前！=rear ) {v=Q[ front]； arcNode *p=adjlist[v].firstedge； while(p！=null}{intj=p-adjvex； if(visited[j]==0) {coutadjlist[j].vertex； visited[j]=1； Q[ rear]=j； }}} }