深度优先搜索中的跟踪和返回路径

深度优先搜索中的跟踪和返回路径

没错，您不能简单地返回堆栈，它确实包含许多未访问的节点。

但是，通过维护map（字典）：

map:Vertex->Vertex

这样

parentMap[v] = the vertex we used todiscover v

，您可以得到自己的路径。

您需要做的修改几乎是在for循环中：

    for child in children:        stack.push(child[0])        parentMap[child] = parent #this line was added

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

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

请注意，顺序将颠倒，可以通过将所有元素压入堆栈然后打印来解决。

我曾经回答过一个类似的（尽管不是完全相同的IMO）问题，关于在此线程中查找BFS中的实际路径

另一种解决方案是使用DFS的递归版本，而不是迭代+堆栈，一旦找到目标

current

，则将递归中的所有节点都打印回来-
但是此解决方案需要将算法重新设计为递归。

---

PS请注意，

visited

如果图形包含无限分支，则DFS可能无法找到到目标的路径（即使保持一组）。
如果您想要一个完整的算法（如果有的话，总是找到一个解决方案）和最优的（找到最短路径）算法-
如果您有启发式功能，则可能要使用BFS或迭代加深DFS甚至A *算法