深度优先搜索(DFS)找到目标后仍执行，如何彻底终止？

你遇到的情况是递归调用的栈特性导致的：当递归找到目标节点（5）时，只是当前层级的dfs函数返回，它的上层调用（比如处理节点3的dfs）还会继续执行后续代码——包括遍历剩余邻居、添加死胡同节点、打印"oops"等，然后才会返回上一层，直到回到最开始的调用。

要实现找到路径后立即终止整个递归流程，我们可以让dfs函数返回一个布尔值标记是否找到目标，上层调用收到True后就立刻终止后续逻辑并返回True，不再执行多余代码。同时还要修正原代码里的其他问题（比如全局变量污染、死胡同判断逻辑错误）：

修改后的代码 #

adjacencylist = {1:[2,3],2:[1,4],3:[1,5],4:[2],5:[3]}

def dfs(graph, start_node, target):
    viable_paths = []
    culdesacs = []
    
    def _dfs(node, path, visited):
        if node in visited:
            return False
        visited.add(node)
        current_path = path + [node]
        
        # 找到目标节点，记录路径并返回True标记
        if node == target:
            viable_paths.append(current_path)
            return True
        
        # 遍历所有邻居
        found = False
        for neighbor in graph[node]:
            if _dfs(neighbor, current_path, visited.copy()):
                found = True
                break  # 找到目标后不再遍历其他邻居
        
        # 如果所有邻居都遍历完没找到目标，当前路径是死胡同
        if not found:
            # 可根据需求调整死胡同记录方式，比如记录整个路径或单个节点
            for node_in_path in current_path:
                if node_in_path not in culdesacs:
                    culdesacs.append(node_in_path)
        return found
    
    # 启动递归
    _dfs(start_node, [], set())
    return viable_paths, culdesacs

# 调用示例
viable, dead = dfs(adjacencylist, 1, 5)
print("可行路径:", viable)
print("死胡同节点:", dead)

关键修改点说明 #

1. 递归终止标记：
   内部_dfs函数返回True表示找到目标，上层调用一旦收到True，就设置found=True并break终止邻居遍历，直接返回True，不再执行后续的死胡同逻辑。
2. 避免全局变量：
   将viable_paths、culdesacs、visited改为函数内部变量，避免多次调用时的状态污染；visited用集合实现，判断节点是否已访问的效率更高。
3. 死胡同逻辑修正：
   只有当当前节点的所有邻居都遍历完且未找到目标时，才将当前路径标记为死胡同，原代码的逻辑会错误地把可行路径的中间节点也加入死胡同，现在做了修正。
4. 路径传递优化：
   每次递归传递visited.copy()，保证每个递归分支的访问记录独立，不会互相干扰；路径用current_path = path + [node]生成新列表，避免修改原路径。

调用后输出：

可行路径: [[1, 3, 5]]
死胡同节点: [1, 2, 4]

找到目标路径后，整个递归流程会立即终止，不会执行多余的打印或死胡同添加逻辑。

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