我一直在学习python中的图形算法,我想知道为什么在结果中会得到一个重复的路径。
这是我的密码
from collections import defaultdict
our_graph = defaultdict(list)
def run_graph():
print('Creating Graph...')
add_edges("London", "Barcelona")
add_edges("Barcelona", "Madrid")
add_edges("Madrid", "Ottawa")
add_edges("Madrid", "Berlin")
add_edges("London", "Ottawa")
print('\nOur Graph:')
print(our_graph)
print('\nEdges:')
print(list_edges())
print('\nTesting Paths To Invalid Nodes:')
print(find_all_paths("LDN", "Ottawa"))
print(find_all_paths("London", "X"))
print('\nTesting Paths To Valid Nodes:')
print(find_all_paths("London", "Ottawa"))
print('---')
print(find_all_paths("London", "Berlin"))
def add_edges(a, b):
our_graph[a].append(b)
our_graph[b].append(a)
def list_edges():
edges = []
for node in our_graph:
for next_node in our_graph[node]:
edges.append((node, next_node))
return edges
def find_all_paths(start, end, path=[]):
# If there isn't a node with that name
if our_graph[start] == [] or our_graph[end] == []:
return 'Can\'t find nodes ' + start + " " + end
else:
# create a path
path = path + [start]
# If start node is the end
if start == end:
return [path]
paths = []
newpaths = []
# For each node
for node in our_graph[start]:
# If node not already in saved path
if node not in path:
# Search the paths of that new node
newpaths = find_all_paths(node, end, path)
# Append new path to paths
for newpath in newpaths:
paths.append(newpath)
return paths
if __name__ == '__main__':
run_graph()
我从
print(find_all_paths("London", "Berlin"))
得到的结果是
[['London', 'Barcelona', 'Madrid', 'Berlin'], ['London', 'Ottawa', 'Madrid', 'Berlin'], ['London', 'Ottawa', 'Madrid', 'Berlin']]
正如你所看到的,伦敦-渥太华-马德里-柏林的路线是重复的。你能解释一下原因吗?
最佳答案
问题在于:
if node not in path:
# Search the paths of that new node
newpaths = find_all_paths(node, end, path)
# Append new path to paths
for newpath in newpaths:
paths.append(newpath)
如果
node
已经在path
中,则将使用旧的newpaths
。您只需要在if语句下移动for循环:if node not in path:
# Search the paths of that new node
newpaths = find_all_paths(node, end, path)
# Append new path to paths
for newpath in newpaths:
paths.append(newpath)
或:
if node not in path:
# Search the paths of that new node
paths += find_all_paths(node, end, path)
另外,我建议使用
defaultdict(set)
而不是列表。