Breadth First Search

Breadth-first search (BFS) is one of the fundamental graph traversal algorithms in computer science. Whether you’re navigating a maze, finding the shortest path in a social network, or crawling web pages, BFS provides an elegant way to systematically explore and analyze connected structures.

What is breadth-first search?

Breadth-first search is an algorithm for traversing or searching tree and graph data structures. It starts at a chosen root node and explores all neighboring nodes at the present depth before moving on to nodes at the next depth level. This layer-by-layer exploration is what gives the algorithm its name. The tree below illustrates how BFS explores nodes level by level, moving systematically through each depth

To better understand BFS, consider this example: imagine you drop a stone into a pond and watch the ripples expand outward in concentric circles, reaching nearby points before distant ones. BFS works the same way, exploring nodes by their distance from the starting point. We begin at the root node on level 1, move to its children on level 2, and finally to its grandchildren on level 3.

How BFS works

The key to breadth-first search lies in its use of a queue data structure. A queue operates on a first-in, first-out (FIFO) principle, meaning the first item added is the first one removed. This ordering is crucial because it ensures we always process nodes in the order we discover them, naturally creating the layer-by-layer exploration pattern. When we visit a node, we add its children to the back of the queue, ensuring they’re processed only after all nodes at the current level have been handled.

The following illustration shows an example of how breadth-first search traverses the nodes of a tree:

1 / 11

Although in BFS, nodes are processed level by level, but the order of traversal within a single level is not strictly defined. While we typically visit nodes from left to right for consistency, BFS does not inherently enforce this direction. The actual order within each level depends on how nodes are added to and removed from the queue during implementation.

Python implementation

Here is a sample implementation of breadth-first search (BFS) traversal that explores the tree level by level using a queue.

from collections import deque

def breadth_first_search(graph, start):
    """
    Perform BFS on a graph starting from a given node.
    """
    
    visited = set()
    queue = deque([start])
    visited.add(start)
    result = []
    
    while queue:
        node = queue.popleft()
        result.append(node)
        
        # Add all unvisited neighbors to the queue
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return result

In general, here is how the algorithm proceeds:

1. Start at the root node and add this node to the queue.
2. Mark the root node as visited by adding it to the visited set.
3. While the queue is not empty:
   1. Remove the front node.
   2. Process this node.
   3. Add all unvisited neighbors to the back of the queue.
   4. Mark these neighbors as visited.

Complexity analysis

Breadth-first search visits nodes in increasing “distance” (number of edges) from the starting node. Its runtime and memory usage depend mainly on how the graph is represented and how many nodes/edges are reachable from the source. Here, V represents the number of vertices (nodes), E represents the number of edges (connections between nodes), and N represents the total number of nodes in a tree.

• Time complexity: O(V + E) for adjacency lists, O(V²) for adjacency matrices, and O(N) for a tree with N nodes.
• Space complexity: O(V) for the visited set and queue, as the queue may hold an entire level at once on wide graphs.

Practical takeaway: BFS is often fast (linear in nodes + edges for adjacency lists) but can be memory-heavy on very wide graphs because it stores the whole current layer.

Examples

The following examples illustrate some problems that can be solved using BFS:

1. Invert binary tree: You are given the root of a binary tree. Your task is to invert the tree and return its root.

BFS is well-suited here because it processes the tree level by level, swapping the left and right children of every node as it goes. At each step, we dequeue a node, swap its two children, then enqueue both children so their subtrees get swapped in turn. By the time the queue is empty, every node in the tree has had its children mirrored, producing the fully inverted result.

2. Minimum depth of a tree: Given a binary tree, return the shortest distance from the root node of the tree to its nearest leaf node.

1 / 4

BFS is ideal here because it naturally finds the shallowest leaf first: as soon as the algorithm dequeues a node with no children, it has found the minimum depth. A depth-first approach would require exploring the entire tree before being certain it had the minimum.

Common applications of BFS

BFS powers many real-world systems and algorithms. Some of the most common applications are listed below:

• Shortest Path Finding: GPS navigation systems use BFS variants to find the shortest route between locations on a road network.
• Social Network Analysis: Finding connections between people, calculating degrees of separation, or suggesting friends based on mutual connections.
• Web Crawling: Search engines use BFS to systematically discover and index web pages by following links.
• Peer-to-Peer Networks: Finding nodes or resources in distributed networks.
• Garbage Collection: Some programming languages use BFS to identify reachable objects in memory.
• Level Order Traversal: In binary trees, BFS naturally produces a level-order traversal.

Best practices and common pitfalls

BFS is powerful, but it’s not foolproof. Here are a few things to watch out for:

• Avoiding cycles: Always track visited nodes. Otherwise, you might loop forever in cyclic graphs.
• Disconnected graphs: If your graph isn’t fully connected, you may need to run BFS from multiple starting points to cover everything.
• Memory usage: BFS can consume a lot of memory, especially in wide or dense graphs, since it stores all nodes at the current “level.”
• Choosing BFS vs. DFS: Use BFS for shortest paths and level-order tasks. DFS is better for exploring deep structures or when memory is tight.