6-2 实现基于邻接表表示的深度优先遍历

深度优先遍历是一种图遍历算法，它从一个起始顶点开始，沿着一条路径尽可能深地访问图中的顶点，直到该路径最后一个顶点没有未访问的邻居为止。然后回溯到前一个顶点，继续访问它的其他未访问邻居，直到所有顶点都被访问为止。

基于邻接表表示的深度优先遍历可以通过递归实现。具体步骤如下：

1. 从起始顶点开始，将其标记为已访问。
2. 遍历该顶点的邻居列表，对于每个未访问的邻居，递归调用深度优先遍历函数。
3. 重复步骤2，直到所有邻居都被访问为止。
4. 回溯到前一个顶点，继续遍历其未访问的邻居。
5. 重复步骤2-4，直到所有顶点都被访问为止。

具体实现可以参考以下代码：

void DFS(int v, bool visited[], vector<int> adj[]) {
    visited[v] = true;
    cout << v << " ";

    for (auto i = adj[v].begin(); i != adj[v].end(); ++i) {
        if (!visited[*i]) {
            DFS(*i, visited, adj);
        }
    }
}

void DFS_traversal(int V, vector<int> adj[]) {
    bool visited[V];
    memset(visited, false, sizeof(visited));

    for (int i = 0; i < V; ++i) {
        if (!visited[i]) {
            DFS(i, visited, adj);
        }
    }
}

其中，DFS函数表示深度优先遍历函数，visited数组用于记录每个顶点是否已经被访问过，adj数组表示邻接表。DFS_traversal函数表示整个图的深度优先遍历过程，V表示顶点数。