如何用DFS在无向邻接表中查找所有源到目标节点的路径

问题描述 #

需要从邻接表中找出源节点到目标节点的所有可行路径，比如起始节点1到目标节点5，期望得到[1,2,3,4,5]和[1,2,6,7,8,5]两条路径。但现有代码只能找到其中一条，核心问题是找到一条路径后，大部分节点被标记为已访问，不知道如何在不陷入无限递归的情况下回溯弹出节点。

现有代码 #

adjacencylist={1:[2],2:[1,6,3],3:[2,4],4:[3,8,5],5:[4],6:[2,7],7:[6,8],8:[7,4]}
visited=[]
viablepaths=[]


def dfs(graph,start,target,path,output):
    if start in visited:
        return
    visited.append(start)
    
    if start==target:
        output.append(path)
        
        viablepaths.extend(output)
        
        return
    for nx in graph[start]:
        dfs(graph,nx,target,path+[nx],output)
    
    
    return 

dfs(adjacencylist,1,5,[1],[])

问题根源 #

1. 全局visited未做回溯：当前代码用全局列表存储已访问节点，一旦节点被加入就不会移除。找到第一条路径1->2->3->4->5后，visited已包含[1,2,3,4,5]，后续尝试走1->2->6->...分支时，节点2已在visited中，直接返回，无法探索第二条路径。
2. 冗余全局变量：viablepaths和output的设计重复，增加了逻辑复杂度。

修复方案 #

核心是加入回溯机制：在递归遍历完当前节点的所有邻接节点后，将当前节点从visited中移除，让其他分支可以重新访问该节点。同时简化全局变量的使用，让函数逻辑更清晰。

修复后的代码 #

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

def dfs(graph, start, target, path, visited):
    # 将当前节点加入路径和已访问集合
    path.append(start)
    visited.add(start)
    
    if start == target:
        # 返回路径副本，避免后续修改影响已记录的路径
        return [path.copy()]
    
    paths = []
    for nx in graph[start]:
        if nx not in visited:
            # 递归探索邻接节点，收集所有子路径
            sub_paths = dfs(graph, nx, target, path, visited)
            paths.extend(sub_paths)
    
    # 回溯：移除当前节点，让其他分支可以访问
    path.pop()
    visited.remove(start)
    
    return paths

# 调用函数，初始化路径为空列表，已访问为空集合（查询效率更高）
viable_paths = dfs(adjacencylist, 1, 5, [], set())
print(viable_paths)

关键改进点 #

• 用集合存visited：集合的成员查询和删除操作效率远高于列表，提升代码性能。
• 显式回溯操作：递归结束后，通过path.pop()和visited.remove(start)将当前节点从路径和已访问集合中移除，确保其他分支可以重新访问该节点。
• 直接返回路径集合：让函数返回找到的所有路径，避免使用全局变量，逻辑更直观。
• 保存路径副本：找到目标节点时返回path.copy()，因为后续的pop操作会修改原路径列表，必须保存副本才能得到正确的路径。

运行结果 #

执行后会输出：

[[1, 2, 3, 4, 5], [1, 2, 6, 7, 8, 4, 5]]

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