深度优先搜索算法

Question

在boost库中实现的深度优先算法只访问一次顶点。

是否有任何解决方法来停用此选项。我希望在任何顶点有分支时都可以访问顶点。

任何建议...

编辑：图为无环的。

Answer 1

如果你想枚举非循环图中的所有路径，那么我认为你不能轻易修改深度优先搜索来做到这一点。有专门为此设计的算法，特别是：Rubin，F .; ，“Enumerating all simple paths in a graph”，Circuits and Systems，IEEE Transactions on，vol.25，no.8，pp.641-642，Aug 1978.

如果你知道Floyd-Warshall算法，可以很容易地修改它来计算矩阵中每个元素的路径列表，而不是最小距离，这将完成这项工作。上面的文章使用了一些操作来使其运行速度更快一些。

Answer 2

希望顶点可以被访问 每当有任何 顶点的分支。

你认为迭代器在到达顶点分支时会做什么？

深度优先搜索只是这个问题的答案之一。 Here是其他一些。

但是你必须选择一些东西。这不是关闭DFS的问题。

Answer 3

我认为这是不可能的设计。因为如果你的图形包含循环（并且你有它们，当你说，这个顶点可以被访问多次），算法将以无限循环结束。