为何Python实现的DFS代码在部分目标节点查询时返回None？

问题描述 #

你编写的DFS代码仅能在目标节点是起始节点直接邻居（如'B'、'C'）时返回正确路径，查询其他节点（如'F'、'J'）时会返回None，无法得到预期路径。

原代码 #

# Using a Python dictionary to act as an adjacency list
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['G', 'H'],
'D' : [],
'E' : ['F'],
'G' : [],
'H' : ['I'],
'F' : [],
'I' : ['J'],
'J' : []
}

visited = [] # Set to keep track of visited nodes of graph.
visited_new = []

def dfs(visited, graph, node, goal): #function for dfs
    if node not in visited:
#         print (visited)
        visited.append(node)
        for neighbour in graph[node]:
#             print(visited)
            if neighbour not in visited:
                dfs(visited, graph, neighbour, goal)
                
            if neighbour == goal:
                idx_goal = visited.index(goal)
                return visited[:idx_goal+1]
        
# Driver Code
print("Following is the Depth-First Search")
print(dfs(visited, graph, 'A', 'C'))

问题根源 #

1. 递归返回值未传递：调用递归dfs时未接收返回结果，导致深层找到的路径无法向上传递到顶层调用
2. 目标判断逻辑局限：仅检查当前节点的邻居是否为目标，忽略了递归深入后找到目标的情况
3. 全局状态污染：visited是全局列表，多次调用会残留之前的访问记录，干扰后续查询

修复后的代码 #

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['G', 'H'],
    'D': [],
    'E': ['F'],
    'G': [],
    'H': ['I'],
    'F': [],
    'I': ['J'],
    'J': []
}

def dfs(graph, node, goal, visited=None):
    # 每次调用初始化visited，避免全局状态残留
    if visited is None:
        visited = []
    if node not in visited:
        visited.append(node)
        # 当前节点就是目标，直接返回路径副本
        if node == goal:
            return visited.copy()
        # 遍历所有邻居节点
        for neighbour in graph[node]:
            # 接收递归查询的结果
            path = dfs(graph, neighbour, goal, visited)
            # 如果找到有效路径，立即返回
            if path is not None:
                return path
        # 回溯：当前节点所有邻居都遍历完未找到目标，移除当前节点
        visited.pop()
    # 节点已访问或无有效路径，返回None
    return None

# 测试验证
print("DFS路径到C:", dfs(graph, 'A', 'C'))
print("DFS路径到F:", dfs(graph, 'A', 'F'))
print("DFS路径到J:", dfs(graph, 'A', 'J'))

修复说明 #

• 局部化访问记录：将visited改为函数内部初始化的参数，避免全局状态污染，每次查询都是独立的状态
• 传递递归结果：递归调用时接收返回的路径，一旦找到目标就立即向上传递，保证路径能返回至顶层
• 回溯机制：当当前节点的所有邻居都遍历完毕仍未找到目标时，将当前节点从visited中移除，保证路径的准确性
• 目标判断前移：先检查当前节点是否为目标，覆盖所有节点的匹配场景，不再仅局限于邻居节点

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