views:

609

answers:

9

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.

+2  A: 

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

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

Dario
+4  A: 

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.

sepp2k
It seems like it would have to be a pretty extreme case for a BFS to take up less space than a DFS though, considering that the space complexity of a BFS is b^d.
Jason Baker
After refreshing myself on what b and d actually mean in my above comment, I remembered that each node having one child node would be 1^d. Thus, I suppose having only one child node *would* be an extreme case. :-)
Jason Baker
+3  A: 

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.

Victor Hurdugaci
So in other words, BFSes are the simplest solution for infinite graphs?
Jason Baker
Not really. It's a naive approach. If you are 100% sure that a solution exists then it could work. But if no solution exists and you don't limit the search then it is not a good approach.
Victor Hurdugaci
+1  A: 

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

Gabriel
How is a BFS the best tool for the job in that case though? Can't that be accomplished using a DFS?
Jason Baker
+1  A: 

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).

Matt Breckon
+1  A: 

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.

kubal5003
Erm... What is WBS?
Jason Baker
Work Breakdown Structure ;)http://en.wikipedia.org/wiki/Work_breakdown_structure
kubal5003
+4  A: 

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.

ziggystar
+2  A: 

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).

Olexiy
A: 

calculate complexity of print shortest path function based on breadth first search

explain how to find the minimum key stored in a b-treeand how to find the predcessor of a given key stored in b-tree .

waheed