如何将使用Yield的DFS迷宫寻路代码改写为带循环的return版本

1 改写含yield的DFS为普通return形式 #

原yield版本的作用是迭代返回所有可达路径，根据你需要的返回结果可选择两种改写方式：

1.1 仅返回第一条找到的路径 #

def dfs_paths(self, start, target, path=None):
    if path is None:
        path = [start]
    if start == target:
        return path
    # 注意：原代码用next作为变量名会覆盖Python内置next函数，此处修改为next_node
    for next_node in self.mazegrid.adjacency[start] - set(path):
        res = self.dfs_paths(next_node, target, path + [next_node])
        if res is not None:
            # 子递归找到路径直接向上返回
            return res
    # 当前分支无可达路径返回空
    return None

1.2 返回所有可达路径 #

def dfs_paths(self, start, target, path=None, result=None):
    if path is None:
        path = [start]
    if result is None:
        result = []
    if start == target:
        result.append(path.copy())
        return result
    for next_node in self.mazegrid.adjacency[start] - set(path):
        self.dfs_paths(next_node, target, path + [next_node], result)
    return result

2 修正explorepath函数并获取路径 #

首先你的原代码存在两个逻辑错误：

• 遍历邻居的循环中，只要第一个邻居递归返回False就直接return False，不会遍历剩余邻居，会漏查绝大多数路径
• 回溯删除节点的逻辑位置错误，应该是遍历完所有邻居都未找到路径再执行回溯
  修正后的代码如下：

def explorepath (self, current, objective, visited_list, path) : 
    if current == objective : 
        # 找到终点后加入路径再返回
        path.append(current)
        return True
    if current in visited_list : 
        return False 
    visited_list.append(current)
    path.append(current)
    
    for neighbor in self.mazegrid.successors(current): 
        if self.explorepath(neighbor, objective, visited_list, path) == True : 
            return True
    # 所有邻居遍历完成仍未找到路径，回溯
    path.pop()
    return False

获取路径的方法非常简单：因为Python中列表是可变对象，你提前初始化空的path和visited列表传入函数，如果函数返回True，你传入的path列表就已经存储了完整的有效路径，调用示例：

visited = []
path = []
if self.explorepath(起点坐标, 终点坐标, visited, path):
    # 此处直接使用path变量即可
    print("找到的路径为", path)
else:
    print("无可达路径")

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