如何在Python迭代式DFS算法中实现目标状态并记录路径？

我来帮你梳理下代码里的问题，以及调整路径记录逻辑的关键点：

原代码的核心问题 #

你的代码里路径列表l和栈的操作完全脱节，而且访问标记、邻接节点判断的逻辑也有问题：

1. 路径只在初始时添加了起点，但后续栈弹出节点时，没有对应处理路径的回溯（比如当某个节点的所有邻接都遍历完，需要从路径里移除这个节点）。
2. 访问标记的时机错误：你在弹出节点后才标记为已访问，而且目标判断放在这个分支里，会导致目标节点可能没被正确识别。
3. 邻接节点的判断条件写错了：Python里逻辑或用or而非||，而且cost[s][i] != -1 or cost[s][i] !=0这个条件永远成立（一个数不可能同时等于-1和0），应该改成cost[s][i] != -1 and cost[s][i] != 0（假设-1表示无连接，0表示节点自身）。
4. 栈只存单个节点，无法追踪路径：DFS回溯时，你不知道当前路径应该回退到哪一步，所以需要让栈和路径绑定。

修正方案1：栈中存储节点+路径（最直观的方式） #

这种方式让栈里的每个元素都包含当前节点和到达该节点的完整路径，避免手动回溯的麻烦：

def DFS_Traversal(cost, start_point, goals):
    num = len(cost)
    visited = [0] * num
    # 栈中存储元组：(当前节点, 到达该节点的路径)
    stack = [(start_point, [start_point])]
    visited[start_point] = 1  # 起点标记为已访问
    
    while stack:
        current_node, current_path = stack.pop()
        
        # 检查当前节点是否是目标，找到就直接返回路径
        if current_node in goals:
            return current_path
        
        # 倒序遍历邻接节点（保证和递归DFS的遍历顺序一致，可选）
        for i in reversed(range(num)):
            # 判断是否有有效连接且未被访问
            if cost[current_node][i] != -1 and cost[current_node][i] != 0 and visited[i] == 0:
                visited[i] = 1
                # 复制当前路径并添加新节点，压入栈
                new_path = current_path.copy()
                new_path.append(i)
                stack.append((i, new_path))
    
    # 没有找到目标节点时返回空列表
    return []

关键调整点：

• 路径与栈绑定：每次压入栈的是「节点+到达该节点的路径」，弹出时直接拿到完整路径，无需单独维护路径列表。
• 路径操作时机：只有当要访问新的邻接节点时，才复制当前路径并添加新节点，保证路径和遍历过程完全同步。
• 访问标记时机：在压入栈前就标记节点为已访问，避免同一个节点被多次压入栈造成循环。

修正方案2：手动维护路径+回溯（更贴近递归DFS的逻辑） #

如果你不想用元组存储路径，也可以通过栈标记节点是否已处理邻接，手动实现路径回溯：

def DFS_Traversal(cost, start_point, goals):
    num = len(cost)
    visited = [0] * num
    stack = []
    current_path = []
    
    # 栈中存储元组：(当前节点, 是否已处理过邻接节点)
    stack.append((start_point, False))
    visited[start_point] = 1
    
    while stack:
        node, is_processed = stack.pop()
        
        if is_processed:
            # 节点的所有邻接都遍历完了，从路径中移除它（回溯）
            current_path.pop()
            continue
        
        # 第一次弹出节点，加入路径
        current_path.append(node)
        
        # 检查是否是目标节点
        if node in goals:
            return current_path
        
        # 标记为待处理状态，重新压入栈
        stack.append((node, True))
        
        # 倒序遍历邻接节点，保证遍历顺序正确
        for i in reversed(range(num)):
            if cost[node][i] != -1 and cost[node][i] != 0 and visited[i] == 0:
                visited[i] = 1
                stack.append((i, False))
    
    return []

关键逻辑：

• 栈里的第二个布尔值标记节点是否已经处理过邻接：
  1. 第一次弹出节点时，将其加入路径，然后把它重新压入栈并标记为「已处理」，再压入所有未访问的邻接节点。
  2. 第二次弹出该节点（标记为已处理），说明它的所有邻接都遍历完成，此时从路径中移除它，实现回溯。

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