Почему выходные данные изменяются в этой реализации Python для Depth First Search?

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)

EDIT:

Также я должен отметить, для чего нужны 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)

Answer 2

Потому что в Python наборы не имеют определенного порядка.Возможно, вы захотите использовать списки вместо наборов.