dfs遍历所有简单路径需用visited标记防环，路径用vector存储便于回溯和访问，到达终点时拷贝路径；应设最大深度和路径总数上限剪枝，注意无向图双向建边、有向图单向建边，visited回溯须在递归返回后、pop_back前。

用 DFS 遍历所有简单路径，避免环

直接递归深搜是主流做法，但必须防止重复访问节点形成环——否则会无限循环或爆炸式生成无效路径。关键不是“走到终点就停”，而是每条路径都必须是简单路径（节点不重复）。

• 维护一个 visited 容器（如 std::vector<bool></bool> 或 std::unordered_set<int></int>），在进入节点时标记，回溯时撤销
• 起点和终点相同时，也要作为一条合法路径记录（长度为 1 的路径），别漏掉这个边界
• 图用邻接表（std::vector<:vector>></:vector>）比邻接矩阵更省空间，尤其稀疏图

路径存储选 vector 还是 stack？

用 std::vector 当前路径更稳妥。虽然 std::stack 语义上像“路径栈”，但它不支持随机访问，回溯时没法方便地取中间节点或打印整条路径；而 vector 可以直接 push_back/pop_back，且能用 path.back() 获取当前顶点。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

• 每次递归前 path.push_back(u)，返回前 path.pop_back()
• 到达终点时，拷贝一份 path 存入结果容器（如 std::vector<:vector>></:vector>），别存引用
• 如果只关心路径数量而非内容，可改用计数器，省下大量内存

性能爆炸时怎么提前剪枝？

节点数稍大（比如 > 20）或图较稠密时，路径数可能是指数级，不做限制会卡死或 OOM。不能只靠“等它跑完”，得主动设限。

• 加最大深度限制：传入参数 max_len，当 path.size() >= max_len 时直接 return
• 加路径总数上限：全局计数器 count，每次存新路径后 ++，达到阈值就抛异常或设 flag 中断递归
• 对无向图，若已知两点间最短距离为 d，可设 max_len = d + k（k=2~5），避免枚举过绕的路径

有向图 vs 无向图：邻接表构造别写反

邻接表构建方式直接影响路径方向。无向图要双向加边：graph[u].push_back(v); graph[v].push_back(u);；有向图只加单向边：graph[u].push_back(v);。写反会导致漏路径或多路径。

• 调试时打印几条生成路径，检查是否含非法反向边（比如从 B 到 A，但原图中只有 A→B）
• 输入边列表后，建议用 assert(graph[u].size() > 0) 检查起点是否孤立，避免空跑
• 节点编号若非 0-based，记得统一偏移，否则 visited[i] 访问越界

实际写的时候，最容易被忽略的是 visited 状态的回溯时机——必须在递归调用之后、pop_back 之前恢复，顺序错一丁点就会污染后续分支。

C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！