如何在有向图中找到从指定顶点出发长度不超过k的所有简单路径？

推荐算法：深度优先搜索（DFS）+ 回溯 #

这是处理这类「枚举所有简单路径」问题最直接且高效的方案，核心是通过递归遍历+回溯来避免环，同时严格控制路径的跳数上限。

具体实现思路 #

1. 状态记录：每次递归时，需要跟踪三个关键信息：
   • 当前路径（用列表存储节点序列即可）
   • 已访问节点集合（避免重复访问形成环）
   • 当前路径的跳数（即路径中边的数量，等于节点数-1）
2. 递归流程：
   • 从起始节点开始，将其加入当前路径并标记为已访问，若需要可先保存起始节点自身（对应长度为0的路径）。
   • 遍历当前节点的所有邻接节点：
     • 若该节点未被访问，且当前路径跳数+1 ≤ k：
       • 将节点加入路径，标记为已访问
       • 保存这条新路径（跳数为当前跳数+1）
       • 递归处理该邻接节点
       • 回溯：将节点从路径中移除，取消已访问标记，回到上一层继续遍历其他邻接节点
3. 终止条件：当当前路径的跳数达到k时，停止继续递归延伸该路径分支。

为什么不选BFS？ #

BFS并非不能实现，但需要为每个路径分支单独维护已访问节点集合，内存开销会随着路径数量指数级增长，而且逻辑上不如DFS+回溯直观——毕竟路径是线性延伸的，回溯能自然地复用状态，避免冗余存储。

迭代版DFS（可选） #

如果图的规模较大，递归可能导致栈溢出，可以改用迭代版DFS：用栈来保存每个待处理的状态（当前节点、当前路径、已访问集合、邻接节点迭代指针），模拟递归的过程，逻辑和递归版完全一致，只是用栈手动管理状态。

对应你的示例验证 #

以起始节点1、k=3为例：

• 跳数1：遍历1的邻接节点2、3，得到路径1->2、1->3
• 跳数2：从1->3延伸，访问未被标记的2和4，得到1->3->2、1->3->4
• 跳数3：尝试从上述跳数2的路径继续延伸，1->3->2的邻接节点是1（已访问），1->3->4无未访问邻接节点，因此没有符合条件的跳数3路径，和你的示例结果一致。

内容的提问来源于stack exchange，提问作者ivygrowing