回答此问题可获得 20 贡献值,回答如果被采纳可获得 50 分。
<p>下面的代码“蛮力”创建了一个城市图,然后通过DFS运行它以找到最短路径。无论是使用“visted.append(node)”还是“visted=visted+[node]”,我得到的结果都是不同的。添加到列表不正确,找不到最短路径</p>
<p>DFS中的打印是为了调试差异的原因,但我无法确定差异是什么。谁能给我解释一下这个细节吗?谢谢</p>
<pre><code>def CreateGraph(cities):
g={}
for city in cities:
g[city]=[]
return g
def AddRouteToGraph(g,src,dest):
if src in g and dest in g:
g[src].append(dest)
else:
raise ValueError
cities=['Bmore', 'DC', 'SanFran', 'Philly', 'Seattle', 'NYC']
g=CreateGraph(cities)
AddRouteToGraph(g,'Bmore','Seattle')
AddRouteToGraph(g,'Bmore','Philly')
AddRouteToGraph(g,'Philly','NYC')
AddRouteToGraph(g,'DC','NYC')
AddRouteToGraph(g,'SanFran','Philly')
AddRouteToGraph(g,'SanFran','DC')
AddRouteToGraph(g,'SanFran','Seattle')
AddRouteToGraph(g,'Seattle','DC')
def DFS_shortest(g,node,dest,visited,shortest):
visited.append(node)
#visited=visited + [node]
print(f'visited={visited} of type {type(visited)}')
if node==dest:
return visited
for city in g[node]:
if city not in visited:
if shortest!=None:
print(city, str(len(visited)), str(len(shortest)))
else:
print(city, str(len(visited)), 'None')
if shortest==None or len(visited)<len(shortest):
newPath=DFS_shortest(g,city,dest,visited,shortest)
if newPath!=None:
shortest=newPath
return shortest
print(DFS_shortest(g,'Bmore','NYC',[],None))
</code></pre>