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

问题描述

通常，当我不得不走的图形，我一直使用，因为下部空间复杂度深度优先搜索。我诚实地从来没有见过这种情况要求一个广度优先搜索，但我的经验的是的pretty的限制。

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?

更新：我想我的答案<一href="http://stackoverflow.com/questions/1655162/how-do-i-partition-a-bipartite-graph-by-color/1657167#1657167">here显示了一个情况，我已经使用了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屋！