我有一个问题想用深度优先搜索来解决，返回DFS找到的第一条路径。以下是我的（不完整的）DFS函数：

    start = problem.getStartState()    stack = Stack()    visited = []    stack.push(start)    if problem.isGoalState(problem.getStartState):        return something    while stack:        parent = stack.pop()        if parent in visited: continue        if problem.isGoalState(parent):            return something        visited.append(parent)        children = problem.getSuccessors(parent)        for child in children:            stack.push(child[0])

startState和goalState变量只是x, y坐标的元组。problem是一个包含多种方法的类。这里重要的方法是getSuccessors（它返回给定状态的子节点，形式为3项元组的列表。对于这个问题的一部分，只有元组的第一个元素(child[0])重要，它返回子节点的状态，即x, y坐标）和isGoalState（它提供目标状态的x, y坐标）。

所以我认为（目前难以测试），如果其他一切都正确实现，这个函数会在达到目标状态时返回。请告诉我是否遗漏了什么。但我最大的问题是返回什么。我希望它输出从开始到结束到达目标状态的所有状态列表。仅仅返回我的堆栈似乎行不通，因为堆栈会包含许多未访问的子节点。我的访问列表也不会产生任何有用的东西，因为我可能会到达死胡同，不得不回溯，但死胡同的元组仍然在访问列表中。我该如何得到我想要的列表呢？

回答：

你是对的 – 你不能简单地返回堆栈，它确实包含了许多未访问的节点。

然而，通过维护一个映射（字典）：map:Vertex->Vertex，使得parentMap[v] = 我们用来发现v的顶点，你可以得到你的路径。

你需要做的修改主要在for循环中：

    for child in children:        stack.push(child[0])        parentMap[child] = parent #添加了这一行

后来，当你找到目标时，你可以从源到目标获取路径（伪代码）：

curr = targetwhile (curr != None):  print curr  curr = parentMap[curr]

请注意，顺序将是反转的，可以通过将所有元素推入堆栈然后打印来解决这个问题。

我曾经回答了一个类似（但我认为不完全相同）的关于在BFS中查找实际路径的问题，在这个线程中

另一种解决方案是使用DFS的递归版本而不是迭代+堆栈，一旦找到目标，打印递归回溯中的所有current节点 – 但这种解决方案需要将算法重新设计为递归的。

附注：如果图中包含无限分支，DFS可能会无法找到通往目标的路径（即使维护了一个visited集合）。
如果你想要一个完整的（如果存在解决方案总是能找到）和最优的（找到最短路径）算法 – 你可能想使用广度优先搜索或迭代加深DFS，甚至如果有启发式函数，可以使用A*算法