What are the practical factors to consider when choosing between Depth-First Search (DFS) and Breadth-First Search (BFS)? [closed]

by

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.

More Related Contents:

  1. Why DFS and not BFS for finding cycle in graphs
  2. Find all paths between two graph nodes
  3. Breadth First Vs Depth First
  4. Why is the time complexity of both DFS and BFS O( V + E )
  5. Why is depth-first search claimed to be space efficient?
  6. Best algorithm for detecting cycles in a directed graph [closed]
  7. Finding all cycles in a directed graph
  8. Graph Algorithm To Find All Connections Between Two Arbitrary Vertices
  9. Cycles in an Undirected Graph
  10. Why doesn’t Dijkstra’s algorithm work for negative weight edges?
  11. Find the shortest path in a graph which visits certain nodes
  12. Compute the minimal number of swaps to order a sequence
  13. Performing Breadth First Search recursively
  14. Find the paths between two given nodes?
  15. Finding all the shortest paths between two nodes in unweighted undirected graph
  16. How to implement depth first search for graph with a non-recursive approach
  17. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  18. Algorithm to simplify a weighted directed graph of debts
  19. Number of paths between two nodes in a DAG
  20. Explanation of Algorithm for finding articulation points or cut vertices of a graph
  21. How to find the number of different shortest paths between two vertices, in directed graph and with linear-time?
  22. Finding connected components of adjacency matrix graph
  23. Complete graph with only two possible costs. What’s the shortest path’s cost from 0 to N – 1
  24. Comparison-based ranking algorithm
  25. How to convert decimal fractions to hexadecimal fractions?
  26. Convert recursion to tail recursion
  27. Stable separation for two classes of elements in an array
  28. Cache Invalidation — Is there a General Solution?
  29. Distance from a point to a polygon
  30. 64/32-bit division on a processor with 32/16-bit division

Leave a Comment