图数据结构: DFS vs BFS?

Question

关闭。这个问题是 opinion-based 。目前不接受答案。

---

想要改进这个问题吗？更新问题，以便 editing this post 可以用事实和引文来回答它。 .

已关闭 2 年前。

Improve this question

如果给定一个图问题，我们如何知道是否需要使用 bfs 还是 dfs 算法？？？或者什么时候我们使用dfs算法或bfs算法。两者相比有何区别和优势？

Answer 1

BFS 将根据分支因子使用更多内存...但是，BFS 是一个完整的算法...这意味着如果您使用它来搜索尽可能最低深度的内容，BFS 将为您提供最佳结果解决方案。BFS 空间复杂度为 O(b^d)...分支因子提升到深度(可能需要大量内存)。

另一方面，DFS 在空间方面要好得多，但它可能会找到次优的解决方案。这意味着，如果您只是搜索从一个顶点到另一个顶点的路径，则在找到真正的最短路径之前，您可能会找到次优解决方案(并停在那里)。 DFS 空间复杂度为 O(|V|)...这意味着它能占用的最大内存就是最长的可能路径。

它们具有相同的时间复杂度。

从实现上来说，BFS通常使用Queue来实现，而DFS则使用Stack来实现。