algorithm - 如何找到具有固定端节点的图的所有路径（无循环）？

Question

我想找到所有以节点 a 开始并以节点 b 结束的路径。

现在我的解决方案是从 a 开始执行 DFS 并选择路径以 b 结尾。

复杂度是O(egde + node)，能优化到O(path + node)吗？

谢谢！

Answer 1

DFS 有 O(n)，这意味着linear复杂性，它在非排序图中无法改进。