如何调整图的DFS算法，查找'0'到'3'的路径并终止全图遍历

先明确图结构（假设你使用的是如下示例结构，可根据实际情况修改）：

graph = {
    '0': ['1', '2'],
    '1': ['0', '3'],
    '2': ['0', '4'],
    '3': ['1'],
    '4': ['2']
}

原DFS代码（遍历全图） #

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

修改后的目标DFS代码（找0到3的路径，找到即停） #

def dfs_find_path(graph, start, end_vertex, visited=None, path=None):
    # 初始化visited和path（仅第一次调用时执行）
    if visited is None:
        visited = set()
    if path is None:
        path = []
    
    # 标记当前节点已访问，并加入当前路径
    visited.add(start)
    path.append(start)
    
    # 核心终止判断：当前节点就是目标，直接返回路径
    if start == end_vertex:
        return path
    
    # 遍历当前节点的所有邻居
    for neighbor in graph[start]:
        if neighbor not in visited:
            # 递归查找邻居的路径，若找到则直接返回（终止后续遍历）
            result = dfs_find_path(graph, neighbor, end_vertex, visited, path)
            if result is not None:
                return result
    
    # 若当前节点的所有邻居都遍历完仍未找到目标，回溯（从路径中移除当前节点）
    path.pop()
    return None

# 调用示例
target_path = dfs_find_path(graph, '0', '3')
print(target_path)  # 输出: ['0', '1', '3']

关键修改点说明 #

1. 新增参数：添加end_vertex指定目标节点，用path跟踪当前遍历路径（替代单纯的visited集合，因为需要返回具体路径）。
2. 终止判断位置：进入函数后先检查当前节点是否为目标，是则直接返回当前路径，这是最直接的终止触发点。
3. 递归返回值处理：遍历邻居时，递归调用后立刻检查是否返回了有效路径——如果有，直接向上传递返回值，不再继续遍历其他邻居，实现"找到即停"。
4. 回溯处理：如果当前节点的所有邻居都没找到目标，需要把当前节点从路径中移除（回溯），避免影响其他分支的路径记录。

你可能踩的坑 #

如果只单纯加了end_vertex和终止判断，但没处理递归的返回值，会导致找到目标后，函数还会继续遍历其他分支；另外，若只依赖visited集合而不跟踪路径，即使找到目标也无法返回完整的路径结果。

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