Python中列表引用与复制的深度解析：避免DFS路径追踪陷阱

list_a = [1, 2, 3]
list_b = list_a # list_b 现在引用的是和 list_a 相同的对象

list_b.append(4)
print(list_a) # 输出: [1, 2, 3, 4]
print(list_b) # 输出: [1, 2, 3, 4]

res = [] # 用于存储所有路径的结果列表

def find_all_paths_wrong(graph, start_node, target_node):
    def dfs(current_node, current_path):
        if current_node == target_node:
            # 错误做法：直接添加引用
            res.append(current_path)
            return

        # 假设 graph 是一个邻接列表
        for neighbor in graph.get(current_node, []):
            if neighbor not in current_path: # 避免循环
                current_path.append(neighbor)
                dfs(neighbor, current_path)
                current_path.pop() # 回溯：移除当前节点，以便探索其他路径

    path_start = [start_node]
    dfs(start_node, path_start)
    return res

# 示例图
graph_example = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['D'],
    'D': []
}

# 运行错误示例
res = [] # 重置结果列表
wrong_paths = find_all_paths_wrong(graph_example, 'A', 'D')
print("错误结果:", wrong_paths)
# 预期输出可能是 [['A', 'B', 'D'], ['A', 'C', 'D']]
# 实际输出可能是 [[], []] 或其他空列表，因为在回溯时，所有路径都被清空了

import copy

res = [] # 用于存储所有路径的结果列表

def find_all_paths_correct(graph, start_node, target_node):
    def dfs(current_node, current_path):
        if current_node == target_node:
            # 正确做法：添加列表的副本
            res.append(list(current_path)) # 使用 list() 创建副本
            # 或者 res.append(current_path[:]) # 使用切片创建副本
            return

        for neighbor in graph.get(current_node, []):
            if neighbor not in current_path:
                current_path.append(neighbor)
                dfs(neighbor, current_path)
                current_path.pop() # 回溯

    path_start = [start_node]
    dfs(start_node, path_start)
    return res

# 运行正确示例
res = [] # 重置结果列表
correct_paths = find_all_paths_correct(graph_example, 'A', 'D')
print("正确结果:", correct_paths)
# 预期输出: [['A', 'B', 'D'], ['A', 'C', 'D']]