为什么深度优先搜索的这个Python实现的输出会发生变化？

Question

因此，对于深度优先搜索，我在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’]。为什么同一个输入的输出会不同？这个实现是正确的吗？

Answer 1

这是因为你没有考虑到回溯。例如，假设你的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，则只需复制对列表内部列表的引用，就会遇到相同的问题。在这种情况下，从copy导入deepcopy，如下所示：

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)

Answer 2

因为在Python中，集合没有特定的顺序。您可能希望使用列表而不是集合。