algorithm - 查找图中所有路径的理想算法

Question

让我们以这张图为例：

现在假设我从顶点 3 开始并想要找到顶点 7。深度优先搜索（取决于实现）将首先查看子节点。现在，在我们的例子中，为了论证，我从顶点 2 开始，然后去顶点 4 和顶点 2，返回顶点并去顶点 7，问题解决了。

我想要什么：我想获得所有可能的路径，让我从 x 到 y（例如 3 到 7：3,1,4,7 - 3,5,7 - 3,4,7 - 3,5,6,9,7)。我不是从深度优先搜索中得到的。

你建议的算法是什么？

谢谢！

Answer 1

您应该使用修改后的 BFS 算法（http://en.wikipedia.org/wiki/Breadth-first_search）。在每个顶点上，您应该保存通向此顶点（前身）的邻居列表，而不是只有 1 个通向此顶点的邻居。

当你想从中找到所有路径时，你只需要从你的结束节点开始并在每个顶点处分支你的路径，这些顶点有超过 1 个前驱，并按照每个顶点中的前驱创建的方式进行，直到你开始节点您拥有的所有分支机构。

编辑：您可以使用 DSF 算法而不是 BFS 并以相同的方式对其进行修改。