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

Question

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

我实际上感到困惑的是如何计算这两条不同的路径？它们真的不同吗？

例如，考虑以下树，

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

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

1. 对于 BFS

遍历路径： ABCDEFGH

最终路径： ACFH

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

类似地，

2. 对于 DFS

遍历路径： ABDECFG

最终路径： ACFH

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

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

例如，考虑以下场景：

假设在本例中，我们的起始节点是 A，目标节点是 H。

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

但对于最终路径，“H”从两侧可达，从F可达，从G也可达

对于DFS，你可以将最终路径写为ACF 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