Breadth-First Search vs Depth-First Search: Key Differences

How breadth-first search (BFS) works

Breadth-First Search (BFS) is a layer-by-layer traversal technique. Starting from the root node (or any chosen starting point in a graph), BFS explores all the immediate neighbors (i.e., nodes at distance 1), then all nodes at distance 2, and so on. This makes it particularly effective for finding the shortest path in unweighted graphs and trees.

The key data structure used in BFS is a queue (FIFO), which ensures nodes are explored in the order they are discovered.

Algorithm:

1. Initialize a queue and a visited set (or list) to keep track of visited nodes
2. Start by enqueuing the root node and marking it as visited
3. While the queue is not empty:
   • Dequeue a node n from the front
   • Process node n (e.g., print it, check if it’s the goal)
   • Enqueue all unvisited neighbors (or children in a tree) of node n and mark them as visited
4. Repeat until all nodes are explored or the goal is found

Example:

Here is an example that shows breadth-first search in action:

With breadth-first search covered, let’s now focus on depth-first search.

How depth-first search (DFS) works

Depth-First Search (DFS) is a path-oriented traversal technique. It starts from the root (or any chosen node) and explores as far down a branch as possible before backtracking. Unlike BFS, which explores nodes level by level, DFS dives deep into the tree or graph before exploring sibling nodes.

DFS can be implemented in two primary ways:

• Recursively (Implicit stack via function calls)
• Iteratively (Explicit stack)

DFS uses a stack (LIFO) to determine the next node to visit, whether explicitly or through recursion.

Algorithm:

1. Initialize a stack (or use recursion) and a visited set/list
2. Push the root node onto the stack
3. While the stack is not empty:
   • Pop the node from the top
   • If not already visited:
     • Process it (e.g., print or check if it’s the goal)
     • Mark it as visited
     • Push its children onto the stack
4. Repeat until the stack is empty or the goal is found

Example:

Here is an example that shows depth-first search in practice:

Since we’re done discussing both breadth-first search and depth-first search, let’s discover the differences between them.

Differences between breadth-first search and depth-first search

Here are the differences between breadth-first search and depth-first search:

Here, b is the branching factor and d is the depth of the shallowest solution.

Now that we’ve gone through the differences between breadth-first search and depth-first search, let’s see how queues and stacks impact search algorithms.

How queues and stacks impact search algorithms

The queue and the stack are the two data structures that can be used for storing nodes in a search frontier. A queue follows “First In First Out” (FIFO) behavior, where the order the data goes in the queue is the order it leaves the queue. This equates to any line you may have stood on to wait for the bus or to grab a cup of coffee.

A stack follows “Last In First Out” (LIFO) behavior which means that the most recent data added will be the first to leave. To get to a book at the bottom of a stack of books you must first remove the books that were more recently placed in the stack. The different behaviors of the queue and the stack will help define the behavior of the two search algorithms in this article.

Let’s move on to the last topic of this article, which is finding the path to the goal in tree traversal.

Finding the path to the goal in tree traversal

It is important to note that it is not enough to find the node with the correct value. Once the goal node is found using either method of tree traversal, you must be able to provide the path of nodes from the root node to the goal node. This can be done in many ways, from saving paths as you search down the tree to working with trees that can supply the path when needed.

The location of the goal node has a significant impact on determining which search algorithm will be able to find the goal first. That is why these approaches are generally used as building blocks for more complex traversal algorithms. With more information on the location of the goal value in the tree, you can optimize the breadth-first search and depth-first search algorithms. Then they become powerful tools that can help you find that file you were looking for.

Conclusion

Breadth-First Search and Depth-First Search offer different strengths depending on the problem at hand. BFS is generally better for finding the shortest path in unweighted graphs, while DFS is more memory efficient and better suited for scenarios where the solution is likely to be deep in the tree. The choice between the two often depends on the structure of the problem space and the desired outcome.

If you want to learn more about search algorithms, check out the How to Implement Search Algorithms with Python course on Codecademy.

Frequently asked questions

1. Which is faster, BFS or DFS?

It depends. BFS is faster when the solution is near the root, while DFS can be faster when the solution is deep and near the beginning of a branch.

2. Is DFS always recursive?

No. DFS can be implemented using a stack (iterative) or recursion. Both achieve the same result.

3. Can BFS and DFS be used on graphs as well as trees?

Yes. Both BFS and DFS work on trees and general graphs. When used on graphs, it’s important to keep track of visited nodes to avoid cycles.

4. Which search guarantees the shortest path, BFS or DFS?

BFS, when all edges have equal weight, guarantees the shortest path to the goal.

5. Can DFS be modified to find the shortest path?

Not in general. DFS isn’t guaranteed to find the shortest path unless all paths are exhaustively compared, which eliminates its efficiency advantage.