用于查找图中所有路径的理想算法

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).我没有从Depth第一次搜索获得.

您建议的算法是什么？

谢谢!

Answer 1

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

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

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