Practical comparison between Depth-First Search (DFS) Vs Breadth-First serch (BFS)

4 min readFeb 27, 2023

Context

A search algorithm is one that is designed to locate a specific element within a data structure. It consists in solving a problem of the existence or not of a specific element in a finite set of elements, that is, whether or not the element in question belongs to said set, in addition to its location within it.

Types of searching algorithm

The search will depend on the data structure you have. Thus, one can for example do a search in an array, a tree, among other structures.

Search processes involve going through these sturctures of data completely in order to find something. The most common is to search for the smallest or largest element (when it is possible to establish an order), or to search for the index of a particular element.

To search a tree, there are many strategies, and according to your needs, there are two algorithms that are the most efficient for these purposes: Depth-First Search (DFS) and Breadth-First Search (BFS). When to use them? Many of us have asked ourselves that, but know that each one has its advantages and are practical for certain types of search, let’s find out!

Depth-First Search (DFS) vs Breadth-First Search (BFS)

DFS is an algorithm that allows all the nodes of a graph or tree (graph theory) to be traversed in an orderly, but not uniform way. Its operation consists in expanding each and every one of the nodes that it locates, in a recurring way, in a concrete path. When there are no more nodes to visit on that path, return (Backtracking), so repeat the same process with each of the brothers of the node already processed.

Contrary, BFS finds all the vertices that are one edge away from the root, then all the vertices that are two edges away, and so on. This is useful if you’re trying to find the shortest path from the starting node to a given target node. With BFS, you will find the shortest path to the target node. If there were a shorter path, the BFS would have found it already!

But when to use one of these algoriothms? That will depend strongly on the structure of the tree you have and the location of the different results. Here are some heuristics that, in thepry work. You will have of course to experiement the solution that fit you best

If the solution is near the root of the tree, BFS is better
If you have a Deep tree and the solutions are extreme, DFS might take an extremely long time, but BFS could be faster.
If you have a wide tree, BFS will be impractical, since it will take too much memory
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).

The main difference between BFS and DFS is that BFS advances level by level, while DFS first follows a route from the beginning to the end node (vertex), then another route from beginning to end, and so on until all the nodes are visited. In addition, BFS uses a queue to store the nodes, while DFS uses a stack to traverse the nodes.

To end this article, I leave you hete a graphical comparison of both algorithms, choose wisely and follow your needs