When is it practical to use Depth-First Search (DFS) vs Breadth-First Search (BFS)? [closed]

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.

Another issue is parallelism: if you want to parallelize BFS you would need a shared datastructure between threads, which is a bad thing. DFS might be easier to distribute even between connected machines if you don’t insist on the exact order of visiting the nodes.

Related Posts:

  1. Why is the time complexity of both DFS and BFS O( V + E )
  2. Breadth First Search time complexity analysis
  3. Time Complexity of the Kruskal Algorithm?
  4. Performing Breadth First Search recursively
  5. When should I use Kruskal as opposed to Prim (and vice versa)?
  6. Looking for algorithm finding euler path
  7. In a triangulated isometric grid, what triangle is a given point in?
  8. What is a loop invariant?
  9. What is a loop invariant?
  10. What does O(log n) mean exactly?
  11. how to calculate binary search complexity
  12. What does O(log n) mean exactly?
  13. What is Sliding Window Algorithm? Examples?
  14. Quicksort with Python
  15. What is the difference between tree depth and height?
  16. how to implement quick sort algorithm in C++
  17. Python: maximum recursion depth exceeded while calling a Python object
  18. Time complexity of a Priority Queue in C++
  19. What is stability in sorting algorithms and why is it important?
  20. Explanation of runtimes of BFS and DFS
  21. Counting the sum of every nodes’ neighbors’ degrees?
  22. Quick Sort Vs Merge Sort
  23. Polynomial time and exponential time
  24. Insertion Sort vs. Selection Sort
  25. Difference and advantages between dijkstra & A star
  26. Best Case for Bubble Sort
  27. How to find the kth smallest element in the union of two sorted arrays?
  28. Big O, how do you calculate/approximate it?
  29. Is Quicksort in-place or not?
  30. Find how many connected groups of nodes in a given adjacency matrix
  31. longest increasing subsequence(O(nlogn))
  32. O(n log n) vs O(n) — practical differences in time complexity
  33. Trying to understand max heapify
  34. Shortest possible depth of a leaf in decision tree (comparison sorting algorithm)
  35. Python Weighted Random [duplicate]
  36. What is the meaning of “exclusive” and “inclusive” when describing number ranges?
  37. What’s a good algorithm to generate a maze?
  38. Intuition for perceptron weight update rule
  39. Easy: Solve T(n)=T(n-1)+n by Iteration Method
  40. What is tail call optimization?
  41. PacMan: what kinds of heuristics are mainly used?
  42. Quicksort vs heapsort
  43. Big-oh vs big-theta
  44. Best case time complexity for selection sort
  45. Trie complexity and searching
  46. What does this definition of contiguous subsequences mean?
  47. Is log(n!) = Θ(n·log(n))?
  48. Is complexity O(log(n)) equivalent to O(sqrt(n))?
  49. How to find maximum spanning tree?
  50. Exactly how many comparisons does merge sort make?
  51. Algorithm to return all combinations of k elements from n
  52. How to calculate big-theta
  53. What is the time complexity of while loops?
  54. Merge sort time and space complexity
  55. Intuitive explanation for why QuickSort is n log n?
  56. Calculate distance between two latitude-longitude points? (Haversine formula)
  57. Shuffle a deck of cards in Java
  58. How to calculate time complexity of backtracking algorithm?
  59. Median of Medians in Java
  60. What is a loop invariant?
  61. Hash table runtime complexity (insert, search and delete)
  62. Which is better: O(n log n) or O(n^2)
  63. What is O(log* N)?
  64. Quickselect time complexity explained
  65. What is the proper equivalent of “while(true)” in plain C?
  66. Bellman-Ford vs Dijkstra: Under what circumstances is Bellman-Ford better?
  67. Asymptotic Notation – does n (log n) (log n) simplify?
  68. Difference between Big-O and Little-O Notation
  69. What is the big-O of the function (log n)^k
  70. How to calculate an angle from three points?
  71. Why is O(n) better than O( nlog(n) )?
  72. How to solve: T(n) = T(n/2) + T(n/4) + T(n/8) + (n)
  73. Is there an O(n) integer sorting algorithm?
  74. An example of Best Case Scenario for Quick Sort (Need someone to check if my answer is correct)
  75. how to write a recurrence relation for a given piece of code
  76. Why is merge sort worst case run time O (n log n)?
  77. Why is merge sort worst case run time O (n log n)?
  78. What is the time and space complexity of a breadth first and depth first tree traversal?
  79. Create your own MD5 collisions
  80. Image Segmentation using Mean Shift explained
  81. Finding the median of an unsorted array
  82. Difference between Big-Theta and Big O notation in simple language
  83. What is the difference between bucket sort and radix sort?
  84. How are the following functions O(N^3)?
  85. Difference between O(n) and O(log(n)) – which is better and what exactly is O(log(n))?
  86. Finding all possible combinations of numbers to reach a given sum
  87. Are there any real O(n^n) algorithms?
  88. Sorting an array in C?
  89. Is Dijkstra’s algorithm for directed or undirected graphs?
  90. How to determine if a point is in a 2D triangle?
  91. Modular multiplicative inverse function in Python
  92. Minesweeper solving algorithm
  93. About bubble sort vs merge sort
  94. How do I check if an array includes a value in JavaScript?
  95. Kadane’s algorithm explained
  96. Is it more efficient to copy a vector by reserving and copying, or by creating and swapping? [duplicate]
  97. Algorithms in O(n^2) vs O(n) [duplicate]
  98. How to replace all occurrences of a character in string?
  99. Which algorithm is faster O(N) or O(2N)?
  100. Best way to randomize an array with .NET

Leave a Comment