This question already has answers here:
Find all paths between two graph nodes
(11个答案)
7年前关闭。
让我们以该图为例:
现在让我们说我从顶点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)。我没有从深度优先搜索中得到的信息。
您建议的算法是什么？
谢谢!
(11个答案)
7年前关闭。
让我们以该图为例:
现在让我们说我从顶点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)。我没有从深度优先搜索中得到的信息。
您建议的算法是什么？
谢谢!
最佳答案
您应该使用修改后的BFS算法(http://en.wikipedia.org/wiki/Breadth-first_search)。在每个顶点上，您应该保存邻居列表，这些邻居导致该顶点(前身)，而不是只有一个邻居导致该顶点。
当您要从中查找所有路径时，您只需在端节点上开始，并在每个顶点处分支路径即可，该路径具有多个前任，并遵循每个顶点中前任所创建的方式，直到您开始使用您拥有的所有分支。
编辑:
您可以使用DSF算法而不是BFS并以相同的方式对其进行修改。
10-06 13:52