breadth first or depth first search

Question

I know how this algorithm works, but cant decide when to use which algorithm ?

Are there some guidelines, where one better perform than other or any considerations ?

Thanks very much.

Answer 1

If you want to find a solution with the shortest number of steps or if your tree has infinite height (or very large) you should use breadth first.

If you have a finite tree and want to traverse all possible solutions using the smallest amount of memory then you should use depth first.

If you are searching for the best chess move to play you could use iterative deepening which is a combination of both.

IDDFS combines depth-first search's space-efficiency and breadth-first search's completeness (when the branching factor is finite).

Answer 2

BFS is generally useful in cases where the graph has some meaningful "natural layering" (e.g., closer nodes represent "closer" results) and your goal result is likely to be located closer to the starting point or the starting points are "cheaper to search".

When you want to find the shortest path, BFS is a natural choice.

If your graph is infinite or pro grammatically generated, you would probably want to search closer layers before venturing afield, as the cost of exploring remote nodes before getting to the closer nodes is prohibitive.

If accessing more remote nodes would be more expensive due to memory/disk/locality issues, BFS may again be better.

Answer 3

Which method to use usually depends on application (ie. the reason why you have to search a graph) - for example topological sorting requires depth-first search whereas Ford-Fulkerson algorithm for finding maximum flow requires breadth-first search.

Answer 4

If you are traversing a tree, depth-first will use memory proportional to its depth. If the tree is reasonably balanced (or has some other limit on its depth), it may be convenient to use recursive depth-first traversal.

However, don't do this for traversing a general graph; it will likely cause a stack overflow. For unbounded trees or general graphs, you will need some kind of auxiliary storage that can expand to a size proportional to the number of input nodes. In this case, breadth-first traversal is simple and convenient.

If your problem provides a reason to choose one node over another, you might consider using a priority queue, instead of a stack (for depth-first) or a FIFO (for breadth-first). A priority queue will take O(log K) time (where K is the current number of different priorities) to find the best node at each step, but the optimization may be worth it.