java - 何时使用 DFS 和 BFS

Question

这是 Facebook 黑客杯中的图搜索问题。 Problem Link

问题描述: MXN 矩阵我们必须找到从源到目标的最小距离。有改变方向的激光，我们每走一步都会发射激光。

问题:

我使用了社论中描述的相同方法，但我使用的是 DFS 而不是 BFS，我对某些情况的回答是错误的。

如何DFS 正在发挥作用 为什么 DFS 不处理此问题而 BFS 工作。

Code LINK

tHanks

Editorial

Answer 1

这很简单。如果你需要在未加权的图中找到最短路径，你应该使用 BFS。如果您需要特定的遍历顺序(如拓扑排序)，您应该使用 DFS。如果路径的顺序和长度无关紧要，您可以使用它们中的任何一个。在这个问题中需要最短路径，因此 BFS 是一个明显的选择(DFS 不起作用，因为它找到了一些路径，不一定是最短的路径)。