广度优先搜索有什么用?
通常,当我必须遍历图时,我总是使用深度优先搜索,因为空间复杂度较低。老实说,我从未见过需要广度优先搜索的情况,尽管我的经验非常有限。
什么时候使用广度优先搜索有意义?
更新:我想我的答案这里展示了我使用BFS的情况(因为我认为是DFS)。但我仍然很好奇为什么它在这种情况下有用。
Usually when I've had to walk a graph, I've always used depth-first search because of the lower space complexity. I've honestly never seen a situation that calls for a breadth-first search, although my experience is pretty limited.
When does it make sense to use a breadth-first search?
UPDATE: I suppose my answer here shows a situation where I've used a BFS (because I thought was a DFS). I'm still curious to know though, why it was useful in this case.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(10)
还没有人提到广度优先搜索有用的情况下的关键因素:以一种方式访问节点可能会消除以其他方式访问节点的要求。在某些情况下,无论访问节点的顺序如何,最终都会执行相同的工作,但 BFS 一次待处理的操作比 DFS 少得多。在其他情况下,访问一个序列中的节点可能比其他节点需要更多的工作;给出了各种最短路径算法作为示例。如果访问一个节点需要访问其邻居,除非已知该节点可以通过比当前节点短的路径到达,则按广度优先顺序访问节点通常会导致节点被分配最短路径(或接近它的路径) -他们第一次来访时。相比之下,深度优先搜索会导致许多节点第一次被非常长的路径访问,然后通过稍微短的路径,然后稍微短的路径,等等,这需要真正巨大的总工作量。
顺便说一句,深度优先和广度优先算法之间差异的一个很好的图形说明是区域洪水填充,其中通过将白色节点涂成黑色并洪水填充其邻居来进行洪水填充。如果尝试从角落开始淹没 NxN 正方形区域,则深度优先操作将以螺旋或之字形序列填充该正方形,并在堆栈上保留 NxN-1 操作。宽度优先填充将从起始点“倾倒”出来,并且最多有 O(N) 操作待处理,无论要填充的形状如何。顺便说一句,IBM BASICA 中的洪水填充就是这样工作的(我不确定 QBASIC)。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
当你想通过遍历尽可能少的边到达一个节点时,即当你想在未加权的图中找到最短路径时。
此外,当例如每个节点仅具有一个子节点时,即当图很深但不是很宽时,深度优先搜索的空间复杂度可以高于广度优先搜索的空间复杂度。
When you want to reach a node by traversing as few edges as possible, i.e. when you want to find the shortest path in an unweighted graph.
Also the space complexity of a depth first search can be higher than that of a breadth first search when e.g. each node has only one child node, i.e. when the graph is deep but not very broad.