26

通常当我不得不走一个图时，我总是使用深度优先搜索，因为空间复杂度较低。老实说，我从未见过需要广度优先搜索的情况，尽管我的经验非常有限。

什么时候使用广度优先搜索有意义？

更新：我想我在这里的回答显示了我使用 BFS 的情况（因为我认为是 DFS）。不过，我仍然很想知道，为什么它在这种情况下很有用。

4

10 回答 10

14

当您想通过尽可能少的边到达节点时，即当您想在未加权图中找到最短路径时。

此外，当每个节点只有一个子节点时，即当图很深但不是很宽时，深度优先搜索的空间复杂度可能高于广度优先搜索的空间复杂度。

于 2009-11-01T13:32:50.227 回答
7

如果您的搜索域是无限的，深度优先搜索并不能保证终止/找到解决方案，即使确实存在有限解决方案。

您还可以看到更精细的算法，例如 A*，它是广度优先搜索的特殊子类型。

一般来说，bfs 是最优且完整的（具有有限的分支因子），而 dfs 不是。

于 2009-11-01T14:07:10.050 回答
3

可用于以最少的步骤解决搜索问题。首先深入可能会导致（如果不以某种方式受到限制）无限深度。

例如：找到满足条件的最接近根的节点。

于 2009-11-01T13:34:08.790 回答
3

在广度优先搜索有用的情况下，没有人提到一个关键因素：以一种方式访问​​节点可能会消除以其他方式访问节点的要求。在某些情况下，无论访问节点的顺序如何，最终都会做同样的工作，但 BFS 一次待处理的操作要比 DFS 少得多。在其他情况下，按一个顺序访问节点可能比其他节点需要更多的工作；给出了各种最短路径算法作为示例。如果访问一个节点需要访问它的邻居，除非已知该节点可以通过比当前路径更短的路径到达，那么以广度优先顺序访问节点通常会导致节点被分配最短路径——或接近它的路径—— - 在他们第一次访问时。相比之下，

顺便说一句，深度优先和广度优先算法之间差异的一个很好的图形说明是区域泛洪填充，其中白色节点通过将其涂黑并对其邻居进行泛洪填充来进行泛洪填充。如果尝试从角落开始填充 NxN 正方形区域，深度优先操作将以螺旋或之字形序列填充正方形，而 NxN-1 操作保留在堆栈上。广度优先填充将从起点“倾泻”出来，并且无论要填充的形状如何，都最多有 O(N) 次操作待处理。顺便说一句，IBM BASICA 中的洪水填充就是这样工作的（我不确定 QBASIC）。

于 2011-02-04T20:03:43.037 回答
2

一个例子是遍历文件系统（递归深度有限）。

根据wikipedia，它对于某些图形算法（二分性、连通分量）也很有用。

于 2009-11-01T13:32:12.113 回答
2

什么时候使用广度优先搜索有意义？

例如，当您需要在图中找到最短路径时 - DFS 无法做到这一点。还有一些其他的应用程序，但一般来说，DFS 和 BFS 是在不同数据结构上工作的相同算法（BFS 使用队列，DFS 使用堆栈）。

于 2009-11-01T22:19:25.467 回答
1

当您需要从没有边权重的图中获取到顶点的最短路径时。

于 2009-11-01T13:34:27.837 回答
1

在深度优先搜索中，您可能会找到“本地”解决方案 - 要真正找到需要遍历整个图（或使用启发式）的全局解决方案。

于 2009-11-01T13:34:34.230 回答
1

BFS 有时真的很有用。假设您有一棵树，比如说 WBS。您可能只想向您的用户展示它的 1 个级别。

于 2009-11-01T13:35:36.647 回答
1

广度优先搜索算法喜欢尽可能靠近起点。我能想到的一些情况是：

  1. 社交网站可以使用它来查找指定距离内的人。
  2. 在种子下载/点对点网络中查找相邻计算机时很有用。
  3. GPS 导航系统可以使用它来查找附近的位置。
于 2016-05-06T09:45:33.060 回答