何时使用 DFS 和 BFS

Question

这是 Facebook 黑客杯中的图搜索问题。问题链接

问题描述：MXN 矩阵我们必须找到从源到目标的最小距离。在我们采取的每一步中，都有改变方向的激光和也发射激光。

问题：

我使用了在社论中描述的相同方法但是我使用了DFS 而不是 BFS并且我对某些情况的答案有误。

DFS 如何发挥作用 为什么 DFS 在 BFS 工作时没有在这方面工作。

代码链接

tHanks

社论

Answer 1

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