<p>那是因为你还没有考虑回溯。例如,假设你的DFS决定去<code>[‘crocodiles’, ‘lasers’, ‘sharks’, ‘lava’, ‘piranhas’]</code>,这会导致一个死胡同。现在,即使已经到了死胡同,<code>‘lava’, ‘piranhas’</code>已经被追加,所以当您返回到<code>'sharks'</code>并正确地选取<code>'bees'</code>时,列表输出不正确。你知道吗</p>
<p>要解决此问题,只需在从当前节点创建路径之前记录<code>visited</code>。创建路径后,请检查目标节点是否存在,如果不存在,请将<code>visited</code>设置回其原始状态:</p>
<pre class="lang-py prettyprint-override"><code>def dfs(graph, current_vertex, target_value, visited=None):
if visited is None:
visited = []
visited.append(current_vertex)
if current_vertex == target_value:
return visited
for neighbor in graph[current_vertex]:
if neighbor not in visited:
orig = list(visited)
path = dfs(graph, neighbor, target_value, visited)
if path and target_value in path:
return path
visited = list(orig)
</code></pre>
<p>编辑:</p>
<p>我还应该注意到<code>list(visited)</code>和<code>list(orig)</code>是用来做什么的。这样做的原因是(在本例中)深度复制列表。这意味着修改一个将完全独立于另一个。<strong>这只适用于深度为1的列表。如果列表的深度大于1,则只需将引用复制到列表中的列表,然后运行到相同的问题。在这种情况下,通过如下方式导入<code>copy</code>中的<code>deepcopy</code>:</p>
<p><code>from copy import deepcopy</code></p>
<p>编辑2:</p>
<p>最好按以下方式执行,因为您不必存储列表的副本:</p>
<pre><code>def dfs(graph, current_vertex, target_value, visited=None):
if visited is None:
visited = []
visited.append(current_vertex)
if current_vertex == target_value:
return visited
for neighbor in graph[current_vertex]:
if neighbor not in visited:
path = dfs(graph, neighbor, target_value, visited)
if path and target_value in path:
return path
visited.pop(-1)
</code></pre>