python - 深度优先搜索(图形方法)

我已经研究这个问题很长时间了，几乎要解决了基本上，我实现了深度优先搜索，跟踪节点，以便找到目标节点并能够跟踪从开始节点到目标节点的路径。我可以找到目标节点并跟踪路径，但我遇到的问题是：
当我试图重新创建路由时，我陷入了一个无限循环中，比如说，节点x1指向节点x2，节点x2指向节点x1下面是相关的代码（在python中）：

# Starting position
stack = util.Stack()
currentState = problem.getStartState()
goalState = []
directions = {}
visited = []


if problem.isGoalState(currentState): return []
else:
    stack.push(currentState)

while stack.isEmpty() == False:
    currentState = stack.pop()
    if currentState in visited:
        continue
    if problem.isGoalState(currentState):
        goalState = currentState
        break
    visited.append(currentState)
    for state in problem.getSuccessors(currentState):
        stack.push(state[0])
        directions[state[0]] = (currentState, state[1])

print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]

每个状态都是一个元组（（节点坐标），“行进方向”，成本）我知道我需要一个while循环来正确地追溯到开始状态，代码的结尾部分只是向你们展示这个输出：
（1，1）
（二、一）
（二、二）
（二、一）
（二、二）
（二、一）
（二、二）
任何帮助都将不胜感激！这是我第一次在这里发帖，所以我希望我做的一切都是对的。

最佳答案

访问节点时需要保存方向，而不是将节点添加到堆栈时。
在当前代码中，您将继续覆盖方向字典。
（例如，若要解决此问题，可以将新节点和父节点同时保存在堆栈中，然后仅在访问该节点时编写方向字典。）
顺便说一句：
如果使用集合而不是列表，则测试节点是否处于访问状态更有效
如果您想要一个最小成本路径，您可能需要使用优先级队列（如python的heapq模块提供的）而不是堆栈来查找

关于python - 深度优先搜索(图形方法)，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26079394/