图的邻接表存储及遍历重难点

邻接表是一种图的表示方法，它是由一个数组和若干个链表组成的。数组中的每个元素表示一个顶点，对应的链表则存储该顶点的所有邻居顶点。邻接表的存储结构相对于邻接矩阵更加节省空间，适用于稀疏图。

邻接表的遍历主要有两种方法：深度优先搜索（DFS）和广度优先搜索（BFS）。

深度优先搜索是一种递归的遍历算法，在搜索到一个新的顶点时，首先访问该顶点，然后递归地访问它的所有未被访问的邻居顶点。当所有邻居顶点都被访问完毕后，回溯到该顶点的上一个顶点，继续访问其它未被访问的邻居顶点，直到所有顶点都被访问完毕。

广度优先搜索是一种非递归的遍历算法，在搜索到一个新的顶点时，首先访问该顶点，然后将该顶点所有未被访问的邻居顶点加入队列中。接着从队列头取出一个顶点，访问它的所有未被访问的邻居顶点，并将这些邻居顶点加入队列中。重复上述过程，直到队列为空。

在实现邻接表的遍历算法时，需要注意以下重点：

1. 记录每个顶点的访问状态，避免重复访问。
2. 对于深度优先搜索，需要注意回溯时要撤销顶点的访问状态。
3. 对于广度优先搜索，需要使用队列来存储待访问的顶点，并在访问完一个顶点后将其标记为已访问。