广度优先搜索有什么用? [英] What is breadth-first search useful for?

问题描述

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

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?

更新:我想我的答案 此处 显示了我使用 BFS(因为我认为是 DFS)的情况.不过，我仍然很想知道，为什么它在这种情况下有用.

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.

推荐答案

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

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.

这篇关于广度优先搜索有什么用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！