找到解后停止递归并返回：DFS回溯寻路函数问题求助

问题核心 #

递归下层找到路径后，上层调用没有接收到找到路径的信号，会继续遍历同层其他邻居、执行回溯逻辑，因此无法停止。如果直接返回pathfind(nknots)的调用结果，只要某条分支没有找到路径就会直接终止当前层的遍历，不会尝试其他可行分支，导致回溯失效。

最小改动方案 #

方案1：仅返回第一条找到的路径 #

仅需要新增递归返回值校验逻辑，总改动3行：

def pathfind(x):                   
                        
   visited.add(x)
        
   if neighbours[x] != {}:

        for nknots in neighbours[x]:

            if nknots == n:
                
                print("final node is found")
                augpath.append(n)
                return augpath.copy() # 返回路径拷贝，避免后续回溯修改结果
            
            elif nknots in augpath or nknots not in neighbours or nknots in visited:
                
                print("Node already in augpath, visited or has no neighbours: ")
                continue
                        
            else:       
                augpath.append(nknots)

                res = pathfind(nknots)  # 接收递归调用的返回结果
                if res: # 只要下层返回了有效路径，就直接向上传递，停止当前层逻辑
                    return res

                visited.remove(nknots) 
                augpath.pop()
    return None # 未找到路径时返回空

调用时直接接收返回值即可，找到第一条路径后会立刻终止所有递归逻辑返回结果。

方案2：支持逐次返回多条路径（找到一条暂停，下次调用继续找） #

用Python生成器实现，完全匹配你的需求，改动量极小：

def pathfind(x):                   
                        
   visited.add(x)
        
   if neighbours[x] != {}:

        for nknots in neighbours[x]:

            if nknots == n:
                
                print("final node is found")
                augpath.append(n)
                yield augpath.copy() # 找到路径后暂停返回，下次调用从这里继续
                augpath.pop() # 回溯准备找下一条路径
                continue
            
            elif nknots in augpath or nknots not in neighbours or nknots in visited:
                
                print("Node already in augpath, visited or has no neighbours: ")
                continue
                        
            else:       
                augpath.append(nknots)

                yield from pathfind(nknots)  # 透传子递归返回的路径结果

                visited.remove(nknots) 
                augpath.pop()

调用方法：

# 提前初始化全局变量
visited = set()
augpath = [你的起点节点]
path_gen = pathfind(你的起点节点)

# 获取第一条路径
path1 = next(path_gen)
# 获取第二条路径
path2 = next(path_gen)
# 直到抛出StopIteration异常，说明没有更多可行路径

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