How to Implement Breadth-First Search (BFS) in Python

Breadth-First Search (BFS) is a graph traversal algorithm that explores nodes layer by layer. Starting from a root node, it visits all immediate neighbors before moving to the next level of neighbors.

Think of it like ripples in a pond: the search expands outward evenly in all directions.

Primary Use Case: Finding the shortest path in an unweighted graph (for example, the fewest hops between two users in a social network).

Understanding the Algorithm

BFS uses a Queue (First-In-First-Out) data structure:

1. Add the start node to the queue and mark it as visited
2. While the queue is not empty:
   • Remove the first node from the queue
   • Process it
   • Add all unvisited neighbors to the queue and mark them as visited

Level 0:       A
              / \
Level 1:     B   C
            /|    \
Level 2:   D E     F

BFS visits: A → B, C → D, E, F (level by level)

Basic Implementation

Using a Python list as a queue is inefficient because pop(0) is O(n). Always use collections.deque for O(1) operations on both ends.

from collections import deque


def bfs(graph: dict, start: str) -> list:
    """
    Perform BFS traversal starting from the given node.
    
    Args:
        graph: Adjacency list representation of the graph
        start: Starting node for traversal
    
    Returns:
        List of nodes in BFS traversal order
    """
    visited = set()
    queue = deque([start])
    visited.add(start)
    
    traversal_order = []

    while queue:
        vertex = queue.popleft()
        traversal_order.append(vertex)

        for neighbor in graph.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return traversal_order


# Example graph as adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

print(bfs(graph, 'A'))

Output:

['A', 'B', 'C', 'D', 'E', 'F']

Traversal Order

The algorithm visits A (Level 0), then B and C (Level 1), then D, E, and F (Level 2). This level-by-level expansion is what makes BFS ideal for shortest path problems.

Finding the Shortest Path

Modify BFS to track the complete path from start to goal:

from collections import deque


def bfs_shortest_path(graph: dict, start: str, goal: str) -> list | None:
    """
    Find the shortest path between start and goal using BFS.
    
    Returns:
        List representing the path, or None if no path exists
    """
    if start == goal:
        return [start]
    
    queue = deque([[start]])  # Queue stores paths, not just nodes
    visited = {start}
    
    while queue:
        path = queue.popleft()
        node = path[-1]
        
        for neighbor in graph.get(node, []):
            if neighbor == goal:
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(path + [neighbor])
    
    return None

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Find path from A to F
path = bfs_shortest_path(graph, 'A', 'F')
print(f"Shortest path: {path}")
print(f"Distance: {len(path) - 1} edges")

Output:

Shortest path: ['A', 'C', 'F']
Distance: 2 edges

Tracking Distance from Start

When you only need distances rather than full paths:

from collections import deque


def bfs_distances(graph: dict, start: str) -> dict:
    """
    Calculate the shortest distance from start to all reachable nodes.
    """
    distances = {start: 0}
    queue = deque([start])
    
    while queue:
        node = queue.popleft()
        current_distance = distances[node]
        
        for neighbor in graph.get(node, []):
            if neighbor not in distances:
                distances[neighbor] = current_distance + 1
                queue.append(neighbor)
    
    return distances

graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}

# Example graph check distance
distances = bfs_distances(graph, 'A')

for node, dist in sorted(distances.items()):
    print(f"Distance from A to {node}: {dist}")

Output:

Distance from A to A: 0
Distance from A to B: 1
Distance from A to C: 1
Distance from A to D: 2
Distance from A to E: 2
Distance from A to F: 2

BFS on a 2D Grid

BFS is commonly used for maze solving and pathfinding on grids:

from collections import deque


def bfs_grid(grid: list, start: tuple, goal: tuple) -> list | None:
    """
    Find shortest path in a 2D grid using BFS.
    
    Args:
        grid: 2D list where 0 = open, 1 = wall
        start: (row, col) starting position
        goal: (row, col) target position
    """
    rows, cols = len(grid), len(grid[0])
    directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]  # Right, Left, Down, Up
    
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        (row, col), path = queue.popleft()
        
        if (row, col) == goal:
            return path
        
        for dr, dc in directions:
            new_row, new_col = row + dr, col + dc
            new_pos = (new_row, new_col)
            
            # Check bounds, walls, and visited
            if (0 <= new_row < rows and 
                0 <= new_col < cols and 
                grid[new_row][new_col] == 0 and 
                new_pos not in visited):
                
                visited.add(new_pos)
                queue.append((new_pos, path + [new_pos]))
    
    return None


# Example maze (0 = open, 1 = wall)
maze = [
    [0, 0, 0, 1, 0],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]

path = bfs_grid(maze, (0, 0), (4, 4))
print(f"Path through maze: {path}")

Output:

Path through maze: [(0, 0), (0, 1), (0, 2), (1, 2), (2, 2), (2, 3), (2, 4), (3, 4), (4, 4)]

BFS vs DFS Comparison

Feature	BFS	DFS
Data Structure	Queue (FIFO)	Stack (LIFO)
Exploration	Level by level	Deep into branches
Shortest Path	Yes (unweighted)	No guarantee
Memory Usage	Higher (stores frontier)	Lower (stores path)
Best For	Shortest path, nearby nodes	Cycle detection, topological sort

Avoiding Infinite Loops

Always check if neighbor not in visited before adding to the queue. Without this check, cyclic graphs cause infinite loops.

Complexity Analysis

Aspect	Complexity	Notes
Time	O(V + E)	V = vertices, E = edges
Space	O(V)	Queue and visited set storage

Summary

• BFS explores graphs level by level, making it ideal for finding shortest paths in unweighted graphs.
• Always use collections.deque for O(1) queue operations.
• Track visited nodes to prevent infinite loops in cyclic graphs.
• Store paths or distances depending on what information you need.
• BFS works on both abstract graphs and 2D grids.