基于邻接表的深度优先遍历

基于邻接表的深度优先遍历（Depth-First Search, DFS）是一种图遍历算法，在遍历过程中，从某个顶点开始，深度优先遍历会优先访问它的任意一个未被访问过的邻居顶点，然后递归地继续访问该邻居顶点的未被访问过的邻居顶点，直到所有与该顶点直接或间接相连的顶点都被访问过为止。

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

1. 创建一个标记数组 visited，用于记录每个顶点是否被访问过，初始值都设置为 false。

2. 从某个起始顶点开始，递归遍历其邻接表中的每个未被访问过的邻居顶点，将其标记为已访问，然后递归遍历该邻居顶点的邻接表，直到所有与起始顶点直接或间接相连的顶点都被访问过为止。

下面是基于邻接表的深度优先遍历的 C++ 代码实现：

#include <iostream>
#include <vector>
using namespace std;

const int N = 100010; // 最大顶点数
vector<int> adj[N]; // 邻接表
bool visited[N]; // 标记数组

// 深度优先遍历函数
void dfs(int u) {
    visited[u] = true; // 标记顶点 u 已被访问
    cout << u << " "; // 输出顶点 u
    for (int i = 0; i < adj[u].size(); i++) { // 遍历顶点 u 的邻接表
        int v = adj[u][i]; // 取出顶点 u 的第 i 个邻居顶点 v
        if (!visited[v]) { // 如果顶点 v 未被访问过
            dfs(v); // 递归访问顶点 v
        }
    }
}

int main() {
    int n, m; // 顶点数和边数
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v; // 边的起点和终点
        cin >> u >> v;
        adj[u].push_back(v); // 添加一条从 u 到 v 的有向边
        adj[v].push_back(u); // 添加一条从 v 到 u 的有向边
    }
    for (int i = 1; i <= n; i++) {
        if (!visited[i]) { // 如果顶点 i 未被访问过
            dfs(i); // 从顶点 i 开始深度优先遍历
        }
    }
    return 0;
}

在该代码中，变量 adj 表示邻接表，它是一个 vector 的数组，adj[i] 存储顶点 i 的邻接表。变量 visited 是一个 bool 数组，visited[i] 表示顶点 i 是否被访问过。函数 dfs 实现了深度优先遍历，其中参数 u 表示当前访问的顶点。

在主函数中，先读入图的顶点数和边数，然后读入每条边，把邻接表构建出来。最后遍历每个顶点，如果该顶点未被访问过，则从该顶点开始深度优先遍历。