图表数据结构：DFS vs BFS？ [英] Graphs data structure: DFS vs BFS?

问题描述

如果给出图表问题，我们如何知道我们是否需要使用bfs或dfs算法？
或我们什么时候使用dfs算法或bfs算法。
与其他的区别和优点是什么？

解决方案

BFS将使用更多内存，具体取决于分支因子......但是，BFS是一个完整的算法...意味着如果您正在使用它来搜索尽可能最低深度的东西，BFS将为您提供最佳解决方案。
BFS的空间复杂度是 O（b ^ d） ...分支因子提高到深度（可以是很多内存）。

另一方面，DFS对空间好得多，但它可能找不到最理想的解决方案。意思是，如果您只是寻找从一个顶点到另一个顶点的路径，那么在找到真正的最短路径之前，您可能会找到次优解（并停在那里）。 DFS空间复杂度是 O（| V |） ...这意味着它可以占用的最多内存是最长的路径。

它们具有相同的时间复杂度。在实现方面，BFS通常用 Queue ，而DFS使用 Stack 。

if given a graph problem how do we know whether we need to use bfs or dfs algorithm??? or when do we use dfs algorithm or bfs algorithm. What are the differences and advantages of one over other?

解决方案

BFS is going to use more memory depending on the branching factor... however, BFS is a complete algorithm... meaning if you are using it to search for something in the lowest depth possible, BFS will give you the optimal solution. BFS space complexity is O(b^d)... the branching factor raised to the depth (can be A LOT of memory).

DFS on the other hand, is much better about space however it may find a suboptimal solution. Meaning, if you are just searching for a path from one vertex to another, you may find the suboptimal solution (and stop there) before you find the real shortest path. DFS space complexity is O(|V|)... meaning that the most memory it can take up is the longest possible path.

They have the same time complexity.

In terms of implementation, BFS is usually implemented with Queue, while DFS uses a Stack.

这篇关于图表数据结构：DFS vs BFS？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！