Menu
I understand the differences between DFS and BFS, but I'm interested to know when it's more practical to use one over the other?
Could anyone give any examples of how DFS would trump BFS and vice versa?
599
Applications. Depth-first search is used in topological sorting, scheduling problems, cycle detection in graphs, and solving puzzles with only one solution, such as a maze or a sudoku puzzle. Other applications involve analyzing networks, for example, testing if a graph is bipartite.
BFS is better when target is closer to Source. DFS is better when target is far from source. As BFS considers all neighbour so it is not suitable for decision tree used in puzzle games. DFS is more suitable for decision tree.
Breadth-first search is often compared with depth-first search. Advantages: A BFS will find the shortest path between the starting point and any other reachable node. A depth-first search will not necessarily find the shortest path.
Best-first search (BFS) expands the fewest nodes among all admissible algorithms using the same cost function, but typically requires exponential space. Depth-first search needs space only linear in the maximum search depth, but expands more nodes than BFS.
That heavily depends on the structure of the search tree and the number and location of solutions (aka searched-for items).
If you know a solution is not far from the root of the tree, a breadth first search (BFS) might be better.
If the tree is very deep and solutions are rare, depth first search (DFS) might take an extremely long time, but BFS could be faster.
If the tree is very wide, a BFS might need too much memory, so it might be completely impractical.
If solutions are frequent but located deep in the tree, BFS could be impractical.
If the search tree is very deep you will need to restrict the search depth for depth first search (DFS), anyway (for example with iterative deepening).
But these are just rules of thumb; you'll probably need to experiment.
I think in practice you'll usually not use these algorithms in their pure form anyway. There could be heuristics that help to explore promising parts of the search space first, or you might want to modify your search algorithm to be able to parallelize it efficiently.
144
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
