What is breadth-first search useful for?

Usually when I've had to walk a graph, I've always used depth-first sear开发者_开发知识库ch 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.

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.

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.

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.

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

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

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

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

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

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

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.

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.