我有一个字典,其中包含与每个节点关联的父节点和子节点列表(代码中的字典引用)。我将输入一个键(对于下面的代码B
是关键)。我必须考虑父节点。对于B
,我想要路径为[B,C,C1,X],[B,C,C2],[B,D,D1],[B,D,D2]。
我获得的以下代码的输出是:
C ['C1', 'C2']
C1 ['X']
我也收到以下错误:
如果d [i] ['parent'] == [key],在path_find中输入文件“”,第7行:
KeyError:'X'
def path_find(graph,key):
x = d[key]['child']
for i in x:
if d[i]['parent'] == [key]:
print(i,d[i]['child'])
path_find(d,i)
d = {'B':{
'parent' : ['A'],
'child': ['C','D']},
'C':{
'parent' : ['B'],
'child' : ['C1','C2']},
'D':{
'parent' : ['B'],
'child': ['D1','D2']},
'C1':{
'parent' : ['C'],
'child': ['X']}}
key = 'B'
path_find(d,key)
预期的产出是:[B, C, C1, X], [B, C, C2], [B, D, D1], [B, D, D2]
实际输出是:
C ['C1', 'C2']
C1 ['X']
代码中的错误很少:
1)你没有在你的X
中添加关于d = { ... }
节点的信息,这就是你得到KeyError
的原因。我想这是一个没有孩子的节点。
2)您没有将路径保存到当前节点,因此输出无效。
更正的代码(带我的评论):
def path_find(graph, key, current_path, paths_list): # graph, current node key, path to current node, all paths list
if key not in d: # not in graph - no children
paths_list.append(current_path)
return
children = d[key]['child']
for child in children: # check all children
path_find(graph, child, current_path[:] + [child], paths_list)
if not children: # no children - finish search
paths_list.append(current_path)
d = {'B':{
'parent' : ['A'],
'child': ['C','D']},
'C':{
'parent' : ['B'],
'child' : ['C1','C2']},
'D':{
'parent' : ['B'],
'child': ['D1','D2']},
'C1':{
'parent' : ['C'],
'child': ['X']}}
key = 'B'
paths_list = []
path_find(d, key, [key], paths_list)
print(paths_list)
输出:
[['B','C','C1','X'],['B','C','C2'],['B','D','D1'],['B ','D','D2']]