邻接链表（邻接链表深度优先遍历和广度优先遍历）

邻接链表是一种图的存储结构，用于表示图中顶点间的关系和连接。它是图的邻接表的一种改进，适用于存储稀疏图的情况。

## 1. 简介

邻接链表是一种用链表表示图中顶点间关系的方法。相比于邻接矩阵，邻接链表的存储空间更为紧凑，特别适用于存储稀疏图，即图中顶点的连接关系相对较少的情况。

## 2. 多级标题

### 2.1 邻接链表的存储结构

邻接链表由一个顶点数组和一个邻接表链表组成。顶点数组用于存储图中的所有顶点，邻接表链表用于存储每个顶点的邻接关系。

### 2.2 邻接链表的数据结构

邻接链表是由一组以顶点为头结点的链表构成，每个链表中的结点表示一个与该顶点邻接的顶点。

## 3. 内容详细说明

在邻接链表中，我们使用一个顶点数组来存储图中的所有顶点。在构建图时，我们先创建一个空的顶点数组，然后按照顺序将图中的顶点依次存入数组中。每个顶点在数组中的位置将作为该顶点在邻接表中的索引。

对于每个顶点，我们使用一个指针来指向一个链表，这个链表中的结点表示与该顶点邻接的顶点。每个结点包含两个部分：一个表示邻接顶点在顶点数组中的索引，另一个表示指向下一个邻接结点的指针。

当我们查询某个顶点的邻接顶点时，只需要访问该顶点对应的链表，依次遍历链表中的结点即可。在插入或删除顶点时，我们只需要操作对应的链表即可，不需要修改整个顶点数组。

由于邻接链表只存储了图中实际存在的边，所以对于稀疏图而言，邻接链表比邻接矩阵更加节省空间。并且，邻接链表适用于存储动态变化的图，当需要频繁地插入或删除顶点时，邻接链表的效率更高。

总而言之，邻接链表是一种适用于存储稀疏图的数据结构，它通过使用链表表示每个顶点的邻接关系，实现了更加紧凑的存储和高效的操作。