如何在执行 BFS/DFS 算法时从遍历路径中找到最终路径

Question

我正在尝试解决一个问题，该问题在树上应用广度优先搜索算法和深度优先搜索算法，并找出这两种算法找到的遍历路径和最终路径。

我真正困惑的是我如何计算这两条不同的路径？他们真的不同吗？

例如，考虑下面的树，

假设我们的起始节点是A，目标节点是H

对于这两种算法，这就是我认为的遍历路径和最终路径

遍历路径： A B C D E F G H

最终路径： A C F H

如果这是它的工作原理，那么我怎样才能找到最终路径？找到遍历路径很容易，但找到最终路径就没那么容易了。

同样，

遍历路径： A B D E C F G

最终路径： A C F H

同样，如何从 DFS 的遍历路径中提取最终路径。

这实际上变得有点复杂。如果我的目标节点可以从两侧到达怎么办？在这种情况下如何找到最终路径？

例如，考虑以下场景，

假设对于这种情况，我们的起始节点是 A，目标节点是 H。

遍历路径很容易用 BFS 和 DFS 计算。

但是对于Final Path来说，"H"可以从两侧到达，可以从F到达，也可以从G到达

对于 DFS，您可以将最终路径写为 A C F G 因为从 F 节点，我们将首先到达 H（因为 G 仍未探索，但是您会仍然必须从遍历路径中提取此最终路径，我不知道该怎么做）

但是对于BFS，你不能那样做。那么，在这种情况下我的最终路径是什么？在这种情况下应该有两条最终路径吗？

谁能帮我解决这个问题。

Answer 1

一种[在许多可能的]方法中是维护目标到源节点的映射。每次推进时，记录是哪个源节点进行了推进。所以，在 BFS 情况下，它看起来像：

parents = {
  'A': NULL,
  'B': 'A',
  'C': 'A',
  'D': 'B',
  'E': 'B',
  'F': 'C',
  'G': 'C' 
}

然后，从最后一个节点开始，逆向重建路径：

node = target
path = []
while node:
   path.append(node)
   node = parents[node]

同样的方法适用于 DFS 和 Dijkstra

How to find the Final Path from the Traversal Path while performing BFS/DFS algorithm