Breadth-First Search vs Depth-First Search

Overview of BFS and DFS

Let’s start with an overview of what BFS and DFS do. In a breadth-first search, the algorithm looks through every node in the tree at a specific depth before going further down:

Image from Wikipedia
Image from Wikipedia

When to Use Either Method

So what are the differences between these methods? Well, a good rule of thumb is to check the “shape” of your tree, and to use the method that has to check the least possibilities. When you have a wide breadth of possibilities, meaning your algorithm doesn’t have to go super deep but has to check a lot of possibilities (e.g. 3 levels with 10 possibilities each), use DFS. Using BFS would take up a lot of memory and have to go through every possibility before moving to the next level, making it impractical. On the other hand, if your algorithm only has a few possibilities at each node but goes for a long time, use BFS. This prevents a DFS from going all the way down a long, fruitless branch.

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store