c++ - 深度优先搜索算法

Question

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

是否有任何解决方法可以禁用此选项。我希望只要任何顶点中有分支，就可以访问这些顶点。

任何建议...

编辑：该图是非循环的。

Answer 1

希望只要任何顶点中有分支，就可以访问顶点。

您建议迭代器在到达顶点处的分支时做什么？

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

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

Answer 2

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

Answer 3

如果您想枚举非循环图中的所有路径，那么我认为您无法轻松修改深度优先搜索来做到这一点。有专门为此目的设计的算法，特别是：Rubin, F.；, “枚举图中所有简单路径”，《电路与系统》，IEEE Transactions on，第 25 卷，第 8 期，第 641-642 页，1978 年 8 月。

如果您知道 Floyd-Warshall 算法，则可以轻松修改它以计算矩阵每个元素中的路径列表，而不是最小距离，这将完成这项工作。上面的文章使用了一些位操作来使这个运行得更快一点。