查找在向图周期的所有路径，给出的源点 [英] Find all paths with cycles in directed graph, given the source vertex

问题描述

我有解决这个问题的麻烦。我一定要找到所有的简单的从源点出发的路径的取值的包含的简单的循环有向图。即不重复路线为单一重复的顶点在哪里循环联接回来的道路上，除了允许的。

I'm having trouble solving this problem. I have to find all simple paths starting from a source vertex s containing a simple cycle in a directed graph. i.e. No repeats allowed, except of course for the single repeated vertex where the cycle joins back on the path.

我知道如何使用DFS访寻，如果图有周期的，但我不能找到一种方法，用它来找到所有这样的路径从取值的开始。

I know how to use a DFS visit to find if the graph has cycles, but I can't find a way to use it to find all such paths starting from s.

例如，在该图中

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

从启S ，STABCA将正确地找到的路径。但路径STADCA不会被发现，因为顶点C被标记为已访问由DFS

Starting from s, the path S-T-A-B-C-A will correctly be found. But the path S-T-A-D-C-A will not be found, because the vertex C is marked as Visited by DFS.

可有人暗示我该如何解决这个问题呢？ 谢谢

Can someone hint me how to solve this problem? Thanks

推荐答案

这其实是一个相当简单的算法，比DFS更简单。您只需枚举的所有的一个天真的递归搜索路径，记住不要递归任何进一步的任何时间的道路循环回自己：

This is actually quite an easy algorithm, simpler than DFS. You simply enumerate all paths in a naive recursive search, remembering not to recurse any further any time the path loops back on itself:

（这仅仅是一个Python风格的伪code，我希望这是很清楚。）

(This is just a Python-inspired pseudocode. I hope it's clear enough.)

 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)

这篇关于查找在向图周期的所有路径，给出的源点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！