寻找图中所有路径的理想算法

Question

6

让我们以这张图为例： graph

假设我要从顶点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）。这是深度优先搜索无法提供的。

你会推荐什么算法呢？

谢谢！

- None None

1

如果你不在第一个可接受的解决方案处停止搜索，那么你就可以从深度优先搜索中得到这个结果。因此，不要只说“问题已解决”，而是要记录下解决方案并继续进行。 - jlahd

这个问题似乎不属于本站的范畴，因为它属于计算机科学。 - Alma Do

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maciej Oziębły · Accepted Answer

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

当您想要查找从此处开始的所有路径时，您只需从结束节点开始，在具有多个前任的每个顶点上分支您的路径，并按照每个顶点中前任创建的方式走到具有所有分支的起始节点。

编辑：您可以使用DSF算法代替BFS并以相同的方式进行修改。