查找两组节点之间的路径

Question

我有个图表。我希望获得源节点和目标节点之间的所有可能路径。

我正在寻找一个执行算法，因为我必须对两个节点集(源和目标)这样做。

让我们举个例子。

​

考虑到这个图表，我想得到以下所有可能的路径：

• sources = [0, 4, 5]
• targets = [2, 3]

其结果应该是：

• 0-1-2
• 0-1-2-3
• 4-3
• 4-3-2
• 4-3-2
• 5-4-3
• 5-4-3-2

Answer 1

利用深度优先搜索可以解决两个节点之间所有路径的枚举问题。不过，有几点是值得考虑的。

1. 如果允许输入图包含循环并允许路径中的节点重复，则在一对节点之间可能存在无限多条路径。
2. 即使不允许重复节点，给定的一对节点之间的路径数也可能在输入的节点数中呈指数增长；因此，有必要澄清什么是“性能”算法，因为通常的多项式有界运行时复杂度不合格--输出可能在输入的大小上呈指数增长。