First search by width or depth

Question

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

Are there any recommendations where it is better to follow any other or any considerations?

Many thanks.

Answer 1

If you want to find a solution with as few steps as possible or if your tree has infinite height (or very large), you must first use the width.

If you have a finite tree and you want to go through all possible solutions using the least amount of memory, then you must first use the depth.

If you are looking for the best chess move to play, you can use an iterative recess , which is a combination of both.

IDDFS combines search depth and search efficiency with the width of the first search (when the branch ratio is finite).

Answer 2

BFS is usually useful when the graph has some significant “natural stratification” (for example, closer nodes represent “closer” results) and your goal result is more likely to be closer to the starting point or the starting point is “ cheaper to look for. "

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

If your graph is infinite or programmed, you probably want to find closer layers before you go, since the cost of exploring remote nodes before getting into narrower nodes is prohibitive.

If access to more distant sites would be more expensive due to memory / disk / locality issues, BFS might be better again.

Answer 3

Which method you usually use depends on the application (i.e. the reason you have to look for a graph) - for example, topological sorting requires a depth search, while the Ford-Fulkerson algorithm to search for the maximum flow requires a width search.

Answer 4

If you cross a tree, then in memory, memory proportional to its depth will be used first. If the tree is reasonably balanced (or has some other limit at its depth), it may be convenient to use a recursive traversal of depth.

However, do not do this to go through the general schedule; this is likely to cause a stack overflow. For unlimited trees or general graphs, you need some kind of auxiliary storage that can expand to a size proportional to the number of input nodes. In this case, bypassing the width is simple and convenient.

If your problem has a reason to select one node differently, you can use a priority queue instead of a stack (for the first) or FIFO (for the first). The 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 optimization may be worth it.