题目六 图的遍历 题目要求 基于邻接表存储的图，进行深度优先遍历和广度优先遍历

深度优先遍历（Depth-First Search, DFS）和广度优先遍历（Breadth-First Search, BFS）是图的两种基本遍历算法，适用于有向图和无向图。

深度优先遍历利用递归或栈实现，它尽可能深地搜索图的分支。具体步骤如下：
1. 从图中的一个顶点开始访问，标记该顶点为已访问。
2. 访问未被访问的与当前顶点相邻的顶点，并递归地进行深度优先遍历。
3. 如果当前顶点的所有相邻顶点都被访问过，则回溯到上一个顶点，继续搜索其它路径。

广度优先遍历使用队列实现，它逐层从近到远地访问图的所有顶点。具体步骤如下：
1. 从图中的一个顶点开始访问，标记该顶点为已访问，并将它入队。
2. 当队列非空时，出队一个顶点，并访问它。
3. 将该顶点的所有未访问的邻接点入队。
4. 重复步骤2和3，直到队列为空。

下面是基于邻接表存储的图，进行深度优先遍历和广度优先遍历的伪代码示例：

// 图的深度优先遍历伪代码
void DFS(int vertex, vector<bool>& visited, const vector<vector<int>>& adjList) {
    visited[vertex] = true;
    cout << vertex << " ";
    for (int neighbor : adjList[vertex]) {
        if (!visited[neighbor]) {
            DFS(neighbor, visited, adjList);
        }
    }
}

// 图的广度优先遍历伪代码
void BFS(int startVertex, const vector<vector<int>>& adjList) {
    vector<bool> visited(adjList.size(), false);
    queue<int> q;
    visited[startVertex] = true;
    q.push(startVertex);
    
    while (!q.empty()) {
        int currentVertex = q.front();
        q.pop();
        cout << currentVertex << " ";
        
        for (int neighbor : adjList[currentVertex]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

在实际编程实现时，你需要根据具体的编程语言和数据结构进行相应的调整。