尝试在Python中使用DFS recursive查找图中的所有路径

Question

我找到了一个前几次贴出来的解决方案，我试着把它应用到我的练习中，但它不起作用。 我有一个有节点和边的类图和一个childrenOf方法，它给出了一个节点的所有子节点。这一切都很好。这是我的DFS搜索代码，我想找到所有路径：

def myDFS(graph,start,end,path=[]):
path=path+[start]
if start==end:
    return path
paths=[]
for node in graph.childrenOf(start):
    if node not in path:
        paths.extend(myDFS(graph,node,end,path))            
return paths

我只有空名单。我需要看哪里？当我做path=myDFS时。。。我至少有最后一条路。我尝试了path+=myDFS，但没有成功。图形是成功创建的，因此它不是来自它。谢谢

Answer 1

因为您只想获取从头到尾的所有路径，所以当路径到达末尾时，会将路径附加到总路径列表中。不返回路径的总列表，而是填充：

paths = []

def myDFS(graph,start,end,path=[]): 
    path=path+[start] 
    if start==end:
        paths.append(path) 
    for node in graph.childrenOf(start):
        if node not in path:
            myDFS(graph,node,end,path)

Answer 2

我将嵌套dicts的JSON放平（深度为4）

{'output':
    'lev1_key1': 'v11',
    'lev1_key2': {
       {'lev2_key1': 'v21',
        'lev2_key2': 'v22',
       }
 }

的递归调用

^{pr2}$

结果是

{
 'output/lev1_key1': 'v11',
 'output/lev1_key2/lev2_key1': 'v21',
 'output/lev1_key2/lev2_key2': 'v22',
}