哪一个更适合设计一个算法，在有向图中产生两个顶点之间的所有路径？
回溯
分而治之
贪婪的方法
动态编程
由于BFS和DFS，我正在考虑回溯，但我不确定 . 谢谢 .
请注意，输出中可能存在指数数量的路径 . 实际上，在每个对 i < j 具有边 i -> j 的 n 顶点的有向图中，从 1 到 n 有2n-2个路径：除了 endpoints 之外的每个顶点都可以存在于路径中或被省略 . 因此，如果我们真的想要输出所有路径（而不是，例如，制作一个聪明的惰性结构以便逐个列出它们），那么没有先进的技术可以帮助实现多项式复杂性 .
i < j
i -> j
n
1
找到所有简单路径的最简单方法是递归地构造路径，并在到达末端顶点时将当前路径添加到答案中 . 为了改进它，我们可以使用backtracking . 实际上，对于每个顶点，我们可以首先计算最终顶点是否可以从它到达，并在多项式时间内这样做 . 之后，我们只使用答案为正的顶点 .
1 回答
请注意，输出中可能存在指数数量的路径 . 实际上，在每个对
i < j具有边i -> j的n顶点的有向图中，从1到n有2n-2个路径：除了 endpoints 之外的每个顶点都可以存在于路径中或被省略 . 因此，如果我们真的想要输出所有路径（而不是，例如，制作一个聪明的惰性结构以便逐个列出它们），那么没有先进的技术可以帮助实现多项式复杂性 .找到所有简单路径的最简单方法是递归地构造路径，并在到达末端顶点时将当前路径添加到答案中 . 为了改进它，我们可以使用backtracking . 实际上，对于每个顶点，我们可以首先计算最终顶点是否可以从它到达，并在多项式时间内这样做 . 之后，我们只使用答案为正的顶点 .