如何修改迭代式DFS算法以输出从源节点到目标节点的直接路径

我来帮你搞定这个问题！你当前的代码之所以会输出所有访问过的节点，是因为你用path变量记录了所有遍历过的节点，而不是追踪当前正在探索的单条路径。要实现仅输出源到目标的直接路径，我们需要调整栈的存储逻辑——让栈里保存的不是单个节点，而是从源节点到当前节点的完整路径。这样当我们找到目标节点时，直接返回这条路径即可。

修改后的代码 #

def dfs_non_recursive(graph, source, goal):
    if source is None or source not in graph:
        return "Invalid input"
    # 栈中存储的是当前探索的完整路径，初始路径仅包含源节点
    stack = [[source]]
    while stack:
        current_path = stack.pop()
        current_node = current_path[-1]
        
        # 找到目标节点，直接返回当前路径
        if current_node == goal:
            return current_path
        
        # 遍历当前节点的所有邻居，生成新路径并入栈
        for neighbor in graph[current_node]:
            new_path = current_path.copy()
            new_path.append(neighbor)
            stack.append(new_path)
    
    # 若遍历完所有路径仍未找到目标，返回提示
    return "Path not found"

# 测试示例
graph = {"A": ["D", "F", "B"], "B": ["C"], "C": [], "D": ["E"], "E": ["G"], "F": [], "G": []}
DFS_path = dfs_non_recursive(graph, "A", "G")
print(DFS_path)  # 输出: ['A', 'D', 'E', 'G']

关键改动说明 #

• 栈的存储内容变更：不再存储单个节点，而是存储从源节点到当前节点的完整路径。每个栈元素都是一条独立的探索路径，避免了不同分支的节点互相干扰。
• 路径追踪逻辑优化：每次弹出栈顶的路径后，取路径最后一个节点作为当前探索的节点。如果这个节点是目标，直接返回这条路径，这就是我们要的源到目标的直接路径。
• 新路径生成：遍历当前节点的邻居时，复制当前路径并添加邻居节点，形成新路径后压入栈。这样每个分支的路径都是独立的，不会混合其他分支的节点。
• 移除全局访问记录：不再需要原来的path变量记录所有访问过的节点，因为每条路径本身就完整记录了探索轨迹。

为什么原代码会输出所有节点？ #

原代码中的path变量是全局累加所有访问过的节点，当DFS回溯时（比如从B分支回到A，再去探索D分支），之前访问过的B、C并没有从path中移除，导致最终path包含了所有走过的节点，而不是仅保留到目标节点的那条路径。

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