邻接表用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); } } } 常见错误：
立即学习“C++免费学习笔记（深入）”；
- 忘记传
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 本身不复杂，错就错在边界和意图没对齐。