Breadth-First Search (BFS)

By Kenny Polyak and Mike Mroczka | Last updated: July 24, 2023

An essential aspect of working with graphs and trees is understanding how to traverse the search space. Traversal is the process of systematically visiting each node exactly once following a specific order or pattern. This allows us to search for a node or to trace a specific path through the data structure.

Unlike a linear data structure like an array or a linked list - where each node points to only one subsequent node - graphs and trees offer multiple distinct paths to take through the structure. The example below illustrates the many paths that exist through a tree and the single path through a linked list.

Different traversal algorithms will produce different traversal orders - knowing which to deploy and when enables us to solve problems more efficiently, and sometimes offers the only way to solve a particular problem. Let's look at how a specific traversal algorithm can be used! At the highest level, there are two main traversal algorithms: Depth-First Search (DFS), which is further distinguished with pre-order, in-order, and post-order traversal when specifically considering DFS in a binary tree, and Breadth-First Search (BFS). In this article, we'll focus on BFS.

Keep in mind that while we can manipulate the traversal path with different algorithms, unless the data structure is ordered in a particular way (like a BST) or our algorithm applies additional logic to omit certain paths, each traversal algorithm will ultimately visit each node once. DFS and BFS are considered blind search algorithms as they do not apply any domain-driven heuristic. Instead, the algorithms only apply traversal rules and a terminal case to determine if a goal state is reached.

Note: Since trees are merely directional, acyclic graphs, we'll just refer to both as graphs in the remainder of this article. Everything discussed below is relevant to trees as well as generic graphs, and in cases where that's not true, it will be pointed out as such.

What is Breadth-First Search (BFS)?

Breadth-first search (BFS) is an algorithm for traversing tree or graph data structures. Given a node, the algorithm explores all the neighbor nodes first before moving to the next level neighbors, repeating this process until there are no more nodes to visit.

Unlike depth-first search, which traverses as far as possible down a branch as it processes nodes, breadth-first search explores the graph level by level - it's often also referred to as level-order traversal. The result is that all the nodes on a single level are visited at once and grouped together.

Starting at the root node, the algorithm visits all the neighbor nodes of a particular node, as well as all the neighbor nodes of the parents at the same level as our current node, before moving to the next level.

BFS Implementation

BFS typically uses a queue data structure to store the nodes that are waiting to be explored, guaranteeing a FIFO processing order. When a node is visited, all its neighbors are added to the queue in the order they are found. The next node that is visited is grabbed from the front of the queue, whose neighbors are also added to the queue - the queue ensures that nodes are visited in the order they were added. The process continues until all the nodes have been explored or a target state is found.

Here's an overview of the BFS algorithm:

1. Create a visited set to keep track of visited nodes to avoid revisiting them.
2. Create a queue data structure (FIFO) to store the nodes to be processed.
3. Enqueue the starting node onto the queue and mark it as visited.
4. While the queue is not empty, perform the following steps:
   • Dequeue a node from the front of the queue.
   • Process the dequeued node (e.g., print or perform operations).
   • Enqueue all unvisited neighbors of the dequeued node onto the queue and mark them as visited.
5. Repeat step 4 until the queue becomes empty.

Imagine we have a graph with the following node structure:

Node Class Example

class Node:
    def __init__(self, id):
        self._id = id
        self._neighbors = []

BFS will iteratively add elements to a queue processing all the neighbor nodes until none are left.

Graph Class Example

from collections import deque

class Graph:
    def __init__(self):
        self.visited = set()

def bfs(self, start_node):
        queue = deque([start_node])

# Mark the starting node as visited
        self.visited.add(start_node)

while queue:
            # Dequeue a node from the front of the queue
            current_node = queue.popleft()

# Process the dequeued node
            print(current_node.id)

for neighbor in current_node.neighbors:
                if neighbor not in self.visited:
                    # Enqueue unvisited neighbors
                    queue.append(neighbor)
                    # Mark the neighbor as visited
                    self.visited.add(neighbor)

# Create Nodes and add neighbors
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node1.add_neighbor(node2)
node2.add_neighbor(node3)

# Create a Graph object and perform BFS
g = Graph()
g.bfs(node1)

BFS is useful for finding the shortest path between two nodes in a graph or finding the shortest path from a source node to all other nodes in a graph. It is also used for finding all nodes in a graph that are at a certain distance from a given node.

Time and Space Complexity

• Time complexity: O(V + E), where V is the number of vertices and E is the number of edges.
• Space complexity: O(V), where V is the number of vertices. This primarily depends on the storage of the visited vertices and the queue used for traversal.

When to Use BFS in Technical Interviews

• Finding the shortest distance between two nodes: Problems that require finding the shortest path between nodes are surely meant to test your understanding of BFS. This is often implemented in problems that involve a matrix or a graph that models some physical space, where we are asked to find the shortest distance between two particular cells. BFS prioritizes the nearest nodes first when traversing, which means we can use it to find the shortest path between two nodes, or the minimum number of steps required to reach a goal node or condition.
• When we need to compare a parent to its direct children: Since BFS explores all neighbors of a node before moving on to the next level, this algorithm is useful in scenarios where we want to consider all the children before moving on.
• When we need to print or analyze data by level in the graph or tree: BFS tracks all nodes at a given level, which is useful when we need to batch together all nodes that are at a given level in a tree, or graph, relative to some starting node.
• When we want to visit nodes in increasing order of their distance from a start node: Since BFS allows us to track the depth of the algorithm relative to the starting node, it is useful in scenarios where we need to systematically visit nodes at increasing depths from a start node.

Common Mistakes in Interviews Featuring BFS

• Misunderstanding the tradeoffs and benefits between DFS and BFS: Both may work, but specific cases highlight when to use BFS for shortest paths, for example.
• Not using the correct supporting data structure: BFS requires a queue, while DFS uses a stack. Identify and implement accordingly.
• Forgetting to track visited nodes: Essential to avoid infinite loops in undirected graphs.
• Choosing BFS over DFS when it's not needed: Understand the strengths and weaknesses of both algorithms for backtracking and traversal.

Common BFS Interview Questions

Number of Islands

Problem: Given a 2D matrix, where "1" represents land and "0" represents water, count how many islands are present.

Walls and Gates

Problem: You are given a m x n 2D grid initialized with these three possible values. Fill each empty room with the distance to its nearest gate.

Transformation Dictionary

Problem: Given a dictionary of words, determine whether it is possible to transform a given word into another with a fixed number of characters.