用DFS找出指定长度的简单路径

在图论和计算机科学中，寻找图中所有符合条件的路径是常见的问题之一。今天我们将探讨如何使用深度优先搜索（DFS）来找出一个有向图中从给定顶点出发的所有简单路径，这些路径的长度不超过指定的最大长度k。我们将通过一个具体的实例来展示这个过程，并讨论DFS的优势和一些需要注意的问题。

问题描述

假设我们有一个有向图，其中顶点为1、2、3、4，如下图所示：

1 / \ 2 ← 3 \ / 4

我们需要找出从顶点1出发，所有长度不超过3的简单路径（即路径中不能重复经过同一个顶点）。

算法选择

深度优先搜索（DFS）是解决此类问题的理想算法。与广度优先搜索（BFS）不同，DFS更适合于探索所有可能的路径，因为它会尽可能深入搜索每个分支，直到不能继续为止，然后回溯并探索其他分支。

实现思路

1. 递归函数：我们定义一个递归函数genPaths，它接受图的邻接表、当前节点、剩余的路径长度k以及当前路径。
2. 路径记录：使用一个集合（Set）来记录路径上的节点，避免形成循环。
3. 回溯：当搜索到最大深度k或发现循环时，函数会返回并回溯。
4. 路径输出<