Как я могу избежать использования глубокой копии для этого поиска пути графа

Question

Я делаю график поиска от источника до места назначения.Если я добавляю объект пути в массив результатов, он продолжает обновляться, когда я добавляю уникальный путь, поэтому мне приходится копировать его.Как я мог избежать глубокой копии?Есть ли лучший способ решить эту проблему?

Например.начало 'A', конец 'X' -> [['A', 'B'], ['A', 'B', 'E']]

graph = {}

graph['A'] = ['B', 'C', 'E']
graph['B'] = ['A', 'X', 'E']
graph['E'] = ['X', 'B', 'Z']

import copy

def find_paths(start, end, graph):
    res = []
    path = []
    v = dict()
    traverse_paths(start, end, graph, v, path, res)
    return res

def traverse_paths(start, end, graph, v, path, res):
    v[start] = True
    if start in graph:
        path += [start]
        node_list = graph[start]
        if end in node_list:
            res += [copy.deepcopy(path)]
        for node in node_list:
            if node in v:
                continue
            traverse_paths(node, end, graph, v, path, res)

start = 'A'
end = 'X'
print(find_paths(start, end, graph))

Answer 1

Если вы хотите напечатать все пути от начала до конца, то глубокое копирование не разрушит сложность вашего алгоритма. Если вы не копируете глубже, вы просто добавите ссылку на path, что означает, что каждый раз, когда вы меняете path в своих рекурсивных вызовах, path в вашем res также будет меняться. Глубокое копирование было бы лучшим способом избежать этой проблемы.