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

Stack Overflow用户

提问于 2013-09-23 15:09:39

回答 1查看 10.5K关注 0票数 6

让我们以这个图为例：

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

我想要:我想得到从x到y的所有可能的路径(例如3到7: 3,1,4,7 - 3,5,7 -3，7- 3,4,7 - 3,5,6,9,7)。这是我从深度优先搜索得不到的。

你建议的算法是什么？

谢谢!

发布于 2013-09-23 15:23:49

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

当你想从这里找到所有的路径时，你只需要从你的末端节点开始，在每个顶点上分支你的路径，这些节点有超过一个的前置任务，并且按照每个顶点中前置任务创建的方式进行，直到你得到具有所有分支的开始节点。

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

票数 4

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/18953546

复制

相似问题

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