17370845950

邻接表用vector构建，外层索引为顶点编号，内层存邻居；无向图双向加边，有向图单向加边；DFS递归需含当前节点、visited数组和邻接表，缺visited将导致无限递归。

邻接表怎么建：用 vector> 最直接

图的邻接表本质是每个节点维护一个邻居列表。C++ 中最常用、最轻量的方式是 vector>，外层索引代表顶点编号（0-based 或 1-based），内层 vector 存所有邻接点。

注意点：

• 如果顶点数已知（比如 n 个），初始化时就预留空间：vector> graph(n);
• 无向图要双向加边：graph[u].push_back(v); graph[v].push_back(u);
• 有向图只加单向：graph[u].push_back(v);
• 避免重复建边（除非题目允许重边），否则 DFS 可能误入环或多次访问同一节点

DFS 递归函数怎么写：三个核心要素缺一不可

标准 DFS 递归实现必须包含：当前节点、访问标记数组、邻接表。漏掉 visited 就会无限递归（尤其在有环图中）。

void dfs(int u, vector& visited, const vector>& graph) {
    visited[u] = true;
    // 处理当前节点（如输出、计数、存路径等）
    cout << u << " ";
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v, visited, graph);
        }
    }
}

常见错误：

• 忘记传 visited 引用，导致每次递归都是副本，标记无效
• 把 visited 声明在函数内部，每次调用都重置
• 没检查 v 是否越界（尤其当邻接表里存了非法索引时）

从哪个点开始遍历：别默认只跑 dfs(0)

图不一定是连通的。只调用一次 dfs(0) 只能访问到 0 所在的连通分量。要遍历全图，必须对每个未访问节点启动 DFS：

vector visited(n, false);
for (int i = 0; i < n; ++i) {
    if (!visited[i]) {
        dfs(i, visited, graph);
        // 这里可加换行或分隔符，表示一个新连通分量
        cout << "\n";
    }
}

典型场景：

• 求连通分量个数 → 统计外层循环中进入 dfs 的次数
• 判断图是否连通 → 看最终 visited 是否全为 true
• 重建森林结构 → 每次进入 dfs 对应一棵生成树的根

想记录路径或回溯怎么办：加参数 + 回退操作

如果需要输出某条从起点到终点的路径，或做路径相关决策（如找最短路、判断是否存在某约束路径），就得把当前路径存下来，并在递归返回时弹出栈顶：

void dfs_path(int u, int target, vector& visited,
               vector& path, const vector>& graph) {
    visited[u] = true;
    path.push_back(u);
    if (u == target) {
        // 找到目标，可打印或保存 path
        for (int x : path) cout << x << " ";
        cout << "\n";
    } else {
        for (int v : graph[u]) {
            if (!visited[v]) {
                dfs_path(v, target, visited, path, graph);
            }
        }
    }
    path.pop_back(); // 关键：回溯，恢复现场
    visited[u] = false; // 若允许多次经过同一节点（如带权图枚举所有路径），需取消注释
}

容易被忽略的细节：

• path.pop_back() 必须放在递归调用之后、函数返回之前，否则路径残留
• 若题目不允许重复访问节点（大多数 DFS 遍历题），visited[u] = false 不该恢复；只有明确要求“路径可重用节点”时才放开
• 路径过长时，vector& path 传引用避免拷贝开销

实际写的时候，先确认图是否有向、是否带权、是否连通，再决定要不要多起点遍历、要不要回溯、要不要传额外状态。邻接表和 DFS 本身不复杂，错就错在边界和意图没对齐。