Breadth-First Search vs Depth-First Search
Implementing an algorithm to search for an answer is one of the most important and fun parts of a coding competition. However, a common problem programmers encounter is when to use a breadth-first search (BFS) or depth-first search (DFS). Knowing which search to use can save you a lot of unnecessary testing and checking, and also gives you more insight into the algorithms themselves. It’s an invaluable skill to have, as almost any coding challenge will involve one of these two methods.
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:
To do this, it has a “queue” of which sites to visit next, which gets appended onto after a node is visited. For example, after visiting node 2, nodes 5 and 6 would be appended onto the queue. It also keeps track of which nodes it’s visited already to avoid double-checking and adding extra elements into the queue.
DFS goes through one branch all the way to the bottom, then works its way back up:
This one is a bit simpler to implement; just go all the way down a branch, when you hit the end, back up one node and keep going down.
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.
There are a few other things to keep in mind, however. If you want to find the shortest path to a solution, you’ll need to use a breadth-first search. If solutions are very rare, BFS might be faster than DFS as well. If you know a solution will be relatively close to the start, BFS will find it faster; if you know a solution will be further down, DFS might be more useful. Finally, with an infinitely deep tree, you will have to use BFS.
Of course, there is more nuance to when to use both of these that you’ll need experience to uncover. However, these tips will get you quite far, and hopefully help you with your next coding problems. Good luck!
If you liked this article, you can find my website here and my LinkedIn here. Thanks for reading!
