algorithm - 深度优先搜索优于广度优先搜索，反之亦然

Question

我研究了两种图遍历算法，深度优先搜索和广度优先搜索。由于两种算法都用于解决相同的图遍历问题，所以我想知道如何在两者之间进行选择。我的意思是多一个比另一个更有效，或者在特定情况下我会选择一个而不是另一个的任何原因？

谢谢

Answer 1

对我来说主要区别是理论上的。如果你有一个无限大的图，那么 DFS 永远不会找到一个元素，如果它存在于它选择的第一条路径之外。它基本上会继续沿着第一条路径前进，并且永远找不到元素。 BFS 最终会找到该元素。

如果图的大小是有限的，DFS 可能会更快地找到异常值(根和目标之间的距离更大)元素，而 BFS 会更快地找到更近的元素。 DFS 选择浅层元素路径的情况除外。