图形数据结构:DFS与BFS？

Question

如果给出一个图形问题,我们怎么知道我们是否需要使用bfs或dfs算法？或者我们何时使用dfs算法或bfs算法.一个人与另一个人有什么区别和优势？

Answer 1

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

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

它们具有相同的时间复杂性.

在实现方面,BFS通常用 Queue,而DFS使用a Stack.

Answer 2

广度首先搜索兄弟姐妹.深度首先显然是先搜索孩子.所以,我想这取决于你想要做什么样的搜索.跨字段的关系类型搜索可能会适用于bfs,其中层次结构(树,文件夹,等级等)更适合作为dfs.

Answer 3

两种图遍历都承诺一件事：完全遍历图，访问图中的每个顶点。如果您有内存限制，DFS 是一个不错的选择，因为 BFS 占用大量空间。因此，在这两者之间进行选择取决于您的要求。

想要找到图的（强/）连通分量？还是解迷宫？还是数独？使用 DFS。如果仔细观察，Pre-Order、Post-Order 和 In-Order 都是 DFS 的变体。所以，是的，这是一些有趣的应用。

BFS 如果要测试图是否是二部图，请找到需要此类任务的两个节点或应用程序之间的最短路径。