DFS递归函数返回NoneType对象问题求助

先把你的问题和代码贴出来方便分析：

Could someone help me with this recursive function I wrote for a depth-first search.

Path = [start]
Visited = Path

def DFS(start, end, Path, Visited):
    for i in neighbors(start):
        if i == end:
            Path.append(i)
            return Path
        else:
            if i not in Path and i not in Visited:
                path = Path.copy()
                path.append(i)
                Visited.append(i)
                return DFS(i, end, Path=path, Visited = Visited)

Path = DFS(start, end, Path=Path, Visited = Visited)

Somehow the Path is a NoneType object. I don't understand why.

咱们一步一步捋问题所在：

1. 函数缺少默认返回值，导致分支返回None #

这是最直接的原因：Python里如果函数没有显式写return语句，执行完后会默认返回None。看你的代码：

• 当start的所有邻居要么已经在Path/Visited里，要么不是终点时，for循环会走完所有迭代，但函数没有任何return语句，这时候就会返回None，最后赋值给Path自然就变成NoneType了。

2. 循环逻辑有缺陷，没处理回溯情况 #

你现在的代码在遍历邻居时，遇到第一个符合条件的邻居就直接递归返回，完全没考虑这条路径走不通的情况。如果递归调用返回了None（说明这条路径到不了终点），你的函数也会直接把这个None返回，而不会继续尝试其他邻居。

3. Visited和Path的初始化有问题 #

Visited = Path这行是把两个变量指向同一个列表对象，后续对Visited的修改会直接影响Path，这肯定不是你想要的，得改成独立的列表。

修复后的代码示例 #

这里调整了逻辑，解决了上面的问题：

def DFS(start, end, path, visited):
    # 先处理起点就是终点的情况
    if start == end:
        return path
    
    for neighbor in neighbors(start):
        # 找到终点直接返回路径
        if neighbor == end:
            path.append(neighbor)
            return path
        # 没访问过的节点才继续搜索
        if neighbor not in visited:
            visited.append(neighbor)
            new_path = path.copy()
            new_path.append(neighbor)
            # 递归搜索，拿到结果先判断是否有效
            result = DFS(neighbor, end, new_path, visited)
            if result is not None:
                return result
    # 所有邻居都试过了没找到路径，返回None表示此路不通
    return None

# 初始化（替换成你实际的起点和终点）
start = "A"
end = "D"
initial_path = [start]
initial_visited = [start]
path_result = DFS(start, end, initial_path, initial_visited)

if path_result:
    print(f"找到路径: {path_result}")
else:
    print("没有找到可行路径")

修复要点说明 #

• 给函数加上了末尾的return None，明确标记当前路径走不通，上层调用可以继续尝试其他分支；
• 递归后先判断结果是否有效，只有找到有效路径才返回，否则继续遍历下一个邻居；
• 初始化Visited时和Path分开，避免引用同一个列表；
• 增加了起点就是终点的特殊情况处理，避免不必要的循环。

备注：内容来源于stack exchange，提问作者ananta