Python邻接矩阵DFS遍历默认visited列表未重置问题

核心故障原因 #

你遇到的问题是Python的可变默认参数特性导致的：
Python的函数默认参数会在函数定义阶段完成初始化计算，不会在每次调用函数时重新生成。如果默认参数是列表、字典这类可变对象，函数运行时对该对象的修改会被持续保留，后续调用不传对应参数时，会直接使用被修改过的旧对象。

你代码中dfs函数的默认参数visited = [False for _ in range(test.vertices)]，会在函数定义时就生成一个固定的列表，第一次调用DFS时所有被访问过的节点对应的位置都会被设为True，第二次调用不传visited参数时，用的还是第一次调用后被修改过的同一个列表，自然不符合全False的预期。

额外代码问题补充 #

你定义的Graph类构造函数写的是_init_，正确写法应该是前后各两个下划线的__init__，否则类初始化会报错。

修复方案 #

把visited的默认值设为None，在函数内部每次调用时再判断生成新的全False列表：

def dfs(test, vertex, visited=None):
    if visited is None:
        # 每次调用不传visited时，重新生成全新的全False列表
        visited = [False for _ in range(test.vertices)]
    print(visited,vertex)
    matrix = test.adjMatrix 
    if visited[vertex]:
        return 
    visited[vertex] = True 
    for x in range(len(matrix[vertex])):
        if matrix[vertex][x] == 1 and not visited[x]:
            dfs(test,x,visited)

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