Breadth-First Search (BFS)

Overview

Breadth-First Search (BFS) is a graph traversal algorithm that systematically explores all nodes at the current depth level before proceeding to nodes at the next depth level. It uses a queue data structure to maintain a list of nodes to be explored. The algorithm begins at a specified starting node, marks it as visited, and enqueues it. It then iteratively dequeues a node, processes it, and enqueues all its unvisited neighbors.

This level-by-level traversal ensures that BFS always finds the shortest path (in terms of edge count) from the starting node to any other node in an unweighted graph. BFS has several real-world applications. It is used in shortest path problems like finding the minimum number of moves in a game or routing in networks. It is also utilized in social networks to discover connections within a specified number of degrees, web crawlers for crawling web pages layer by layer, and AI search algorithms for finding solutions in state-space representations.

How It Works

BFS works by:

  1. Starting at a specified node and marking it as visited
  2. Adding the starting node to a queue
  3. While the queue is not empty:
    • Dequeue a node
    • Process the node
    • Enqueue all unvisited neighbors
    • Mark neighbors as visited

The queue ensures that nodes are processed in the order they were discovered, maintaining the breadth-first property of exploring all nodes at the current level before moving to the next level.

BFS Algorithm Pseudocode


BFS(start):
    queue = [start]
    visited = {start}          # mark on ENQUEUE, not on dequeue
    while queue is not empty:
        current = queue.dequeue()
        process(current)
        for each neighbor of current:
            if neighbor is not visited:
                mark neighbor as visited     # <-- here, before enqueueing
                queue.enqueue(neighbor)

Mark nodes visited when you enqueue them, not when you dequeue them. This is the single most common BFS bug. If you only mark on dequeue, a node with many in-edges gets pushed onto the queue once per in-edge before it is ever processed — the queue can blow up to O(E) entries, work is duplicated, and the O(V + E) guarantee is lost entirely.

Implementation


from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    while queue:
        node = queue.popleft()
        print(node)  # Process node
        
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return visited

Complexity Analysis

  • Time Complexity: O(V + E) - where V is the number of vertices and E is the number of edges. Each vertex and edge is visited once.
  • Space Complexity: O(V) - requires storage for the queue and the visited set. In the worst case, the queue can contain all vertices.

BFS Framework

  • Initialize a queue with the starting node and mark it as visited.
  • Use a queue data structure to maintain nodes to be explored in order.
  • Process nodes level by level: dequeue a node, process it, then enqueue all unvisited neighbors.
  • Maintain a visited set to avoid revisiting nodes and prevent infinite loops.
  • Continue the loop until the queue is empty, ensuring all reachable nodes are explored.

Applications

  • Shortest Path: Finding shortest path in unweighted graphs
  • Level-Order Traversal: Traversing trees level by level
  • Social Networks: Finding connections within k degrees
  • Web Crawling: Crawling web pages layer by layer
  • Puzzle Solving: Finding minimum moves in games
  • Broadcasting: Spreading information to all nodes

BFS for Shortest Path

BFS can be modified to find the shortest path between two nodes: 


def bfs_shortest_path(graph, start, target):
    """Track parents, then walk backwards once. O(V + E) time, O(V) space."""
    if start == target:
        return [start]

    parent = {start: None}
    queue = deque([start])

    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor in parent:
                continue
            parent[neighbor] = node
            if neighbor == target:
                # Reconstruct by following parents back to the start
                path = []
                while neighbor is not None:
                    path.append(neighbor)
                    neighbor = parent[neighbor]
                return path[::-1]
            queue.append(neighbor)

    return None  # No path found

Storing the whole path in each queue entry — queue.append((neighbor, path + [neighbor])) — is the more obvious approach and is what you will often see, but it copies the path at every step, costing O(V·E) time and O(V²) memory in the worst case. A parent map costs O(V) and reconstructs the path once, at the end.

Useful BFS Variants

  • Multi-source BFS: seed the queue with every source at distance 0. One pass then gives each node its distance to the nearest source — the standard approach for "rotting oranges" style grid problems.
  • 0-1 BFS: when edge weights are only 0 or 1, use a deque and appendleft for 0-weight edges, append for 1-weight edges. This gives shortest paths in O(V + E) without a priority queue — strictly faster than Dijkstra's for this case.
  • Bidirectional BFS: search from both ends and stop when the frontiers meet. Explores roughly O(bd/2) nodes instead of O(bd), a large win on deep searches with a known target.

Popular LeetCode Questions Using BFS

102. Binary Tree Level Order Traversal

Problem: Given the root of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).

Solution: This problem is a perfect application of Breadth-First Search (BFS). The goal is to traverse the tree level by level, collecting all node values at each level into separate lists. The BFS approach naturally processes nodes level by level, which is exactly what this problem requires. We use a queue to maintain nodes at the current level, process all nodes at that level, collect their values, and then move to the next level by adding their children to the queue.

The algorithm starts by enqueueing the root node. Then, for each level, we determine how many nodes are in the current level (the queue size), process exactly that many nodes, collect their values, and enqueue their children. This ensures we process one complete level at a time before moving to the next. The time complexity is O(N), where N is the number of nodes in the tree, as we visit each node exactly once. The space complexity is O(W), where W is the maximum width of the tree (the maximum number of nodes at any level), as the queue can hold at most all nodes at the widest level. 

                    
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

from collections import deque

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        # deque, not a list. list.pop(0) is O(n) because every remaining element
        # shifts down, which would make this whole traversal O(N^2).
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            for _ in range(level_size):
                node = queue.popleft()
                current_level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(current_level)
        
        return result

Related Algorithms

Explore other graph algorithms: