我找到了一个解决方案,张贴了一段时间前,我曾试图将其应用到我的锻炼,但它不起作用。我有一个类图,它有节点和边,还有一个方法childof,它给出了一个节点的所有子节点。这一切都很好。这是我的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,但没有成功。图表是成功创造的,所以它不是来自成功。由于
由于您只想获得从头到尾的所有路径,因此当路径到达末尾时将其添加到总路径列表中。不返回路径的总列表,而是填充路径:
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)
我已经将嵌套字典的JSON平行化(深度为4)
{'output':
'lev1_key1': 'v11',
'lev1_key2': {
{'lev2_key1': 'v21',
'lev2_key2': 'v22',
}
}
与
的递归调用paths = []
_PATH_SEPARATOR = '/'
def flatten(treeroot, path=''):
path=path
if isinstance(treeroot, dict):
for k in treeroot.keys():
s_path = path + _PATH_SEPARATOR + str(k)
flatten(treeroot[k], path=s_path)
elif isinstance(treeroot, str):
path = path + _PATH_SEPARATOR + treeroot
paths.append(path)
elif isinstance(treeroot, list):
# if node has more than one child
for k in treeroot.keys():
s_path = path + _PATH_SEPARATOR + str(k)
flatten(k, path=s_path)
result is
{
'output/lev1_key1': 'v11',
'output/lev1_key2/lev2_key1': 'v21',
'output/lev1_key2/lev2_key2': 'v22',
}