给定源顶点，查找有向图中具有环路的所有路径

我无法解决这个问题。我必须找到所有simple从源顶点开始的路径s含有一个simple有向图中的循环。即不允许重复，当然除了循环在路径上连接回的单个重复顶点。

我知道如何使用 DFS 访问来查找图形是否有循环，但我找不到一种方法来使用它来查找从s.

例如，在此图中

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

从...开始s，将正确找到路径 S-T-A-B-C-A。但是路径S-T-A-D-C-A将不会被找到，因为顶点C被标记为DFS已访问。

有人可以提示我如何解决这个问题吗？ 谢谢

这实际上是一个非常简单的算法，比DFS简单。你只需列举一下all朴素递归搜索中的路径，记住在路径自身循环时不要进一步递归：

（这只是一个受 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)