广度优先搜索有什么用?

发布于 08-10 02:20 字数 301 浏览 11 评论 0原文

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

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

更新:我想我的答案这里展示了我使用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 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(10

愁杀2024-08-17 02:20:50

当你想通过遍历尽可能少的边到达一个节点时,即当你想在未加权的图中找到最短路径时。

此外,当例如每个节点仅具有一个子节点时,即当图很深但不是很宽时,深度优先搜索的空间复杂度可以高于广度优先搜索的空间复杂度。

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.

找个人就嫁了吧2024-08-17 02:20:50

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

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

一般来说,bfs 是最优且完整的(具有有限分支因子),而 dfs 则不是。

If your search domain is infinite, depth-first-search doesn't guarantee to terminate/find a solution, even if a finite solution does exist.

Also you can see more elaborate algorithms like A* to be a special subtype of breadth-first-search.

In general, bfs is both optimal and complete (with finite branching factor) while dfs isn't.

把时间冻结2024-08-17 02:20:50

还没有人提到广度优先搜索有用的情况下的关键因素:以一种方式访问​​节点可能会消除以其他方式访问节点的要求。在某些情况下,无论访问节点的顺序如何,最终都会执行相同的工作,但 BFS 一次待处理的操作比 DFS 少得多。在其他情况下,访问一个序列中的节点可能比其他节点需要更多的工作;给出了各种最短路径算法作为示例。如果访问一个节点需要访问其邻居,除非已知该节点可以通过比当前节点短的路径到达,则按广度优先顺序访问节点通常会导致节点被分配最短路径(或接近它的路径) -他们第一次来访时。相比之下,深度优先搜索会导致许多节点第一次被非常长的路径访问,然后通过稍微短的路径,然后稍微短的路径,等等,这需要真正巨大的总工作量。

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

Nobody has yet mentioned a key factor in cases where breadth-first search is useful: visiting a node one way may eliminate the requirement to visit the node some other way. In some cases, one will end up doing the same work regardless of the order in which nodes are visited, but BFS will have much fewer actions pending at a time than DFS. In other cases, visiting nodes in one sequence may require more work than others; various shortest-path algorithms are given as an example of that. If visiting a node requires visiting its neighbors unless the node is known to be reachable by a path shorter than the current one, visiting nodes in breadth-first order will typically result in nodes being assigned the shortest path--or something close to it--on their first visit. By contrast, a depth-first search would cause many nodes to be visited by very long paths the first time, then by slightly-shorter paths, then slightly-shorter paths, etc. requiring a truly monstrous total amount of work.

BTW, one nice graphical illustration of the difference between depth-first and breadth-first algorithms is an area flood fill, where a white node is flood-filled by painting it black and flood-filling its neighbors. If one tries to flood-fill an NxN square area starting in a cornder, a depth-first operation would fill the square in a spiral or zig-zag sequence, with NxN-1 operations remaining on the stack. A breadth-first fill would "pour" out from the starting point, and have at most O(N) operations pending, regardless of the shape to be filled. BTW, the flood fill in IBM BASICA worked that way (I'm not sure about QBASIC).

怂人2024-08-17 02:20:50

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

根据 wikipedia,它对于某些图算法(二分性、连通分量)也很有用。

One example is traversing the filesystem (with limited recursive depth).

According to wikipedia, it's also useful for certain graph algorithms (bipartiteness, connected components).

远昼2024-08-17 02:20:50

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

例如:找到距离根最近且满足条件的节点。

Could be used for solving a search problem with minimum number of steps.
Going in depth first could lead (if not limited somehow) to infinite depth.

Ex: finding the closest node to the root that satisfies a condition.

泪痕残2024-08-17 02:20:50

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

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

When does it make sense to use a breadth-first search?

For example, when you need to find the shortest path in a graph - DFS just can't do that. There are some other applications, but, in general, DFS and BFS are the same algorithm working on different data structures (BFS uses queue and DFS works with stack).

一城柳絮吹成雪2024-08-17 02:20:50

BFS有时候真的很有用。假设您有一棵代表 WBS 的树。您可能只想向用户展示其中的 1 个级别。

BFS is sometimes really useful. Suppose you have a tree that represents let's say WBS. You may want to present to your user only 1 level of it.

望笑2024-08-17 02:20:50

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

  1. 社交网站可以使用它来查找社交网络中的人
    指定距离。
  2. 它在种子下载/点对点网络中寻找有用
    邻近的计算机。
  3. GPS 导航系统可以使用它来查找附近的位置。

Breadth-first search algorithm likes to stay as close as possible to the starting point. Some of the situations that I can think of are:

  1. Social networking websites can use it for finding the people in the
    specified distance.
  2. It can be useful in torrenting/peer-to-peer network to look for
    neighbouring computers.
  3. GPS navigation systems can use it to find nearby locations.
拍不死你2024-08-17 02:20:50

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

When you need to get the shortest path to a vertex from a graph with no edge weight.

可是我不能没有你2024-08-17 02:20:50

在深度优先搜索中,您可能会找到“局部”解决方案 - 要真正找到全局解决方案,您需要遍历整个图(或使用启发式)。

In depth first search you may find "local" solutions - to truly find a global solution you need to traverse the entire graph (or use a heuristic).

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文