What is breadth-first search useful for?

Question

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.

Answer 1

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.

Answer 2

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.