Python3递归DFS查找全节点遍历目标路径时返回None的问题与优化

• 邻接节点遍历逻辑错位：循环邻接节点时，碰到第一个符合条件的未访问节点就直接return递归结果，完全跳过了其他邻接分支的尝试。只要第一条邻接分支是死路，哪怕后续分支存在合法路径，也会因为提前返回直接终止搜索。
• 递归返回链路断裂：所有死路分支没有明确返回值，默认返回None；同时找到合法路径时，下层递归的返回结果没有被上层分支捕获、逐层向上传递，最终全链路返回None。
• 缺失回溯逻辑：没有实现"分支无效时回退到上一层，尝试其他邻接方向"的流程，本质上是顺着一条路走到黑的遍历，不是完整的DFS回溯。

核心逻辑完全基于递归返回值传递结果，不需要额外传入存储解的sol参数，保持原有函数签名不变：

def traverse(unvisited, start, end, path, edges):
    # 构建当前层级的路径与剩余待访问节点
    current_path = path + [start]
    remaining_unvisited = unvisited.copy()
    remaining_unvisited.remove(start)

    # 触发终止条件：当前节点为终点，且所有待访问节点已全部遍历
    if start == end and not remaining_unvisited:
        return current_path

    # 遍历当前节点的所有邻接节点
    for neighbor in edges[start]:
        # 仅当邻接节点仍在待访问列表中时，进入递归分支
        if neighbor in remaining_unvisited:
            branch_result = traverse(remaining_unvisited, neighbor, end, current_path, edges)
            # 分支返回有效路径时，直接向上传递结果，终止其他分支搜索
            if branch_result is not None:
                return branch_result

    # 当前节点所有邻接分支均走不通，明确返回None标识死路
    return None

针对给定测试用例：

unvisited = [1,3,4,5]
start = 4
end = 5
edges = {1: (4,5), 3: (1), 4: (1,3,5), 5: (1,4)}
print(traverse(unvisited, start, end, [], edges))
# 输出：[4, 3, 1, 5]

搜索流程符合DFS回溯逻辑：先尝试从4出发走邻接节点1的分支，发现该分支无法完成全节点遍历走到终点5，返回None后自动回溯，尝试邻接节点3的分支，最终找到合法路径逐层向上返回。

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