在给定源顶点的情况下,在有向图中查找具有循环的所有路径

Question

我无法解决这个问题.我已经找到所有简单从源顶点开始路径小号含有简单有向图的周期.即,不允许重复,当然除了循环连接回路径的单个重复顶点.

我知道如何使用DFS访问来查找图表是否有周期,但我找不到一种方法来使用它来查找从s开始的所有这些路径.

例如,在此图中

        +->B-+
        |    v
s-->T-->A<---C
        |    ^
        +->D-+

从那里开始s,将正确找到路径STABCA.但是找不到路径STADCA,因为顶点C被标记为DFS访问.

有人能暗示我如何解决这个问题吗？谢谢

Answer 1

这实际上是一个非常简单的算法,比DFS简单.您只需枚举一个简单的递归搜索中的所有路径,记住在路径循环回来的任何时候都不要再递归:

(这只是一个Python启发的伪代码.我希望它足够清楚.)

 def find_paths_with_cycles(path_so_far):
       node_just_added = path_so_far.back()
       for neigh in out_neighbours(node_just_added):
           if neigh in path_so_far:
               # this is a cycle, just print it
               print path_so_far + [neigh]
           else:
               find_paths_with_cycles(path_so_far + [neigh])


 initial_path = list()
 initial_path.append(s)
 find_paths_with_cycles(initial_path)