获取有向循环图中所有可能的路径

Question

我有一个有向循环图，想要找到从给定（或默认根）节点开始的所有可能路径，而无需再次重复相同的路径。

这里，节点“B”、“D”和“C”是循环的。

我的代码：

def find_all_possible_paths(graph, start, path=[]):
    path = path + [start]
    paths = [path]
   
    if len(graph[start]) == 0:
        return [path]
    for node in graph[start]:
        if node not in path:
            newpaths = find_all_possible_paths(graph, node, path)
            for newpath in newpaths:
                paths.append(newpath)
        else:
            return paths
    return paths

print(find_all_paths_wo_end_node(direct_cyclic_graph , 'A'))

**Output** 

[
 ['A'], 
 ['A', 'B'], 
 ['A', 'B', 'D'], 
 ['A', 'B', 'D', 'C'], 
 ['A', 'B', 'D', 'F'], 
 ['A', 'C'], 
 ['A', 'C', 'B'], 
 ['A', 'C', 'B', 'D'], 
 ['A', 'E']
]

**预计**

我只是缺少一条路径，即 ['A'、'C'、'B'、'D'、'F'] 除此之外，我能够获得所有路径。

不确定我的代码中缺少什么。请帮忙。

Answer 1

问题出在这部分：

    else:
        return paths

这打破了循环，同时可能有更多的邻居可以拜访。您应该在当前迭代中不执行任何操作，但仍让循环继续。所以删除这两行代码。

另一个备注：

path

参数的默认值最好不要是可变类型。如果您在多个图表上调用此函数，

path=[]

可能会导致麻烦。相反，将该参数定义为

path=None

并将函数体中的第一个语句更改为：

    path = (path or []) + [start]