深度优先搜索（DFS）中列表+与+=操作为何结果不同？

这真是个经典的Python列表坑！核心原因在于这两种操作对列表的处理方式完全不同——一个是创建新列表，另一个是原地修改原列表，而DFS的递归逻辑非常依赖每个分支拥有独立的路径副本。

先搞懂两个操作的本质区别 #

• path = path + [start]:
  这个操作会把原path列表和[start]拼接，生成一个全新的列表对象，然后赋值给当前作用域的path变量。原来的path列表丝毫不会被改动，每个递归调用里的path都是独立的副本，各分支之间不会互相干扰。

• path += [start]（或path.extend([start])）:
  这是列表的原地修改操作——它直接在原来的列表对象上添加元素，不会创建新列表。这意味着所有指向这个列表的引用（比如递归调用链里的上层函数的path变量）都会看到这个变化，相当于所有递归分支共享同一个路径列表。

结合你的DFS代码分析差异 #

原代码（path = path + [start]）的正确逻辑：

每次递归调用时，都会生成当前路径的独立副本：

1. 初始调用dfs(graph, 'A', 'G')，path从None变成[]，然后生成新列表['A']。
2. 遍历A的邻居B，此时传入递归的path是['A']，生成新列表['A','B']，继续往下走。
3. 同时，当回溯到A的另一个邻居D时，传入的path还是最初的['A']，生成新列表['A','D']，这条分支和B的分支完全独立。
   最终两个分支各自找到到G的路径，输出两个独立的路径列表。

修改后（path += [start]）的错误逻辑：

所有递归分支共享同一个列表，路径被不断叠加污染：

1. 初始调用后，path变成['A']（原地修改）。
2. 进入B分支，path被改成['A','B']，接着到E变成['A','B','E']，再到H→F，此时path已经是['A','B','E','H','F']。
3. 回溯到E后，继续遍历I，path直接在原来的基础上添加I，变成['A','B','E','H','F','I']。
4. 再回溯到E遍历J→G，path变成['A','B','E','H','F','I','J','G']。
5. 最后回溯到A的D分支，此时path还是那个长长的列表，直接添加D→C，最终输出的就是这个被所有分支“踩过”的混乱路径。

验证小例子 #

可以用简单代码直观感受两者的区别：

# 新列表操作
a = [1, 2]
b = a + [3]
print(a)  # 输出 [1,2]，原列表不变
print(b)  # 输出 [1,2,3]，新列表

# 原地修改操作
a = [1, 2]
a += [3]
print(a)  # 输出 [1,2,3]，原列表被修改

解决方法 #

如果你想使用原地修改的写法，也可以手动创建列表副本后再修改，比如：

path = path.copy()  # 或者 path[:]，创建副本
path += [start]

这样每个递归分支还是用独立的列表，就能得到正确结果了。

内容的提问来源于stack exchange，提问作者HelloWorld4444