因此,对于深度优先搜索,我在Python中有一个如下所示的实现:
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:
return path
my_graph = {
'lava': set(['sharks', 'piranhas']),
'sharks': set(['lava', 'bees', 'lasers']),
'piranhas': set(['lava', 'crocodiles']),
'bees': set(['sharks']),
'lasers': set(['sharks', 'crocodiles']),
'crocodiles': set(['piranhas', 'lasers'])
}
但是当我运行print(dfs(my_graph, "crocodiles", "bees"))
时,有时我得到[‘crocodiles’, ‘piranhas’, ‘lava’, ‘sharks’, ‘lasers’, ‘bees’]
,有时我得到[‘crocodiles’, ‘lasers’, ‘sharks’, ‘lava’, ‘piranhas’, ‘bees’]
,有时我得到:[‘crocodiles’, ‘piranhas’, ‘lava’, ‘sharks’, ‘bees’]
。为什么输出在同一输入上不同?这个实现是否正确?
这是因为你还没有计算回溯。例如,假设你的DFS决定去[‘crocodiles’, ‘lasers’, ‘sharks’, ‘lava’, ‘piranhas’]
,这导致死路一条。现在即使它已经到了死胡同,‘lava’, ‘piranhas’
已被追加,所以当你回溯到'sharks'
并正确选择'bees'
时,列表输出不正确。
要解决此问题,您只需在从当前节点创建路径之前记录visited
。创建路径后,检查目标节点是否存在,如果不存在,请将visited
设置回原始状态:
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)
编辑:
另外我应该注意list(visited)
和list(orig)
的用途。这样做的原因是(在这种情况下)深度复制列表。这意味着修改一个将完全独立于另一个。这仅适用于深度为1的列表。如果列表的深度> 1,您只需复制对列表中列表的引用,然后运行相同的问题。在这种情况下,使用deepcopy
中的copy
进行导入,如下所示:
from copy import deepcopy
编辑2:
最好按以下方式执行,因为您不必存储列表的副本:
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)
因为在Python中,集合没有特定的顺序。您可能希望使用列表而不是集合。