BFS for Graphs: A Queue-Based Approach

What is Breadth-First Search?

Imagine dropping a stone into a pond. The ripples spread out evenly in all directions, reaching all points at the same distance from the center at the same time. BFS works just like that. It starts at a source node and explores its immediate neighbors first. Then, it explores the neighbors of those neighbors, and so on. It systematically visits all nodes at a certain "level" or distance before moving on to the next level.

This level-by-level approach makes BFS incredibly useful for a specific and very common category of problems in competitive programming: finding the shortest path between two nodes in an unweighted graph.

To build a strong intuition for this, let's watch a short video that visualizes the BFS process.

As the video explained, the moment BFS reaches a node, it has found the shortest path from the source to that node (in terms of the number of edges). This is a guaranteed property of the algorithm.

The BFS Algorithm and the Role of the Queue

The heart of BFS is the queue. A queue is a data structure that follows a "First-In, First-Out" (FIFO) principle. Think of it like a line at a ticket counter—the first person to get in line is the first person to be served.

This FIFO behavior is what enables the level-by-level traversal. By adding a node's neighbors to the back of the queue, we ensure that we finish exploring all nodes at the current level before moving on to the nodes at the next level.

The algorithm proceeds as follows:

1. Initialize: Create a queue and add the start_node. Create a visited set to track nodes we've already seen, and add the start_node to it.
2. Loop: While the queue is not empty:
   a. Dequeue: Remove the node from the front of the queue. Let's call it current_node.
   b. Process: Do something with current_node (e.g., print it, check if it's the target).
   c. Explore Neighbors: For each neighbor of current_node:
   i. If the neighbor has not been visited:
   - Mark it as visited.
   - Add it to the back of the queue.

This process continues until the queue is empty, meaning all reachable nodes have been visited.

The following image provides a great step-by-step visualization of how the queue's contents change as the algorithm explores the graph.

For a clear textual summary of these steps and the underlying pseudocode, the following article is a useful reference.

Implementing BFS in Python

Now, let's translate this algorithm into Python. We'll use the same adjacency list representation (defaultdict(list)) as in our previous lesson. For the queue, Python's collections.deque is the ideal tool. It's highly optimized for adding (append) and removing (popleft) elements from both ends.

The following video provides a detailed walkthrough of a complete BFS implementation, including tracking not just visited nodes, but also their levels (distance from the source) and parents (to reconstruct the path).

Here is a clean, functional implementation that combines the core ideas from the resources.

from collections import defaultdict, deque

def bfs(graph, start_node):
    """
    Performs a Breadth-First Search on a graph.

    Args:
        graph (dict): The graph represented as an adjacency list.
        start_node: The node to start the traversal from.
    
    Returns:
        list: The order of nodes visited.
    """
    
    # Use a set for O(1) average time complexity for lookups
    visited = {start_node} 
    
    # Use deque for an efficient queue implementation
    queue = deque([start_node])
    
    traversal_order = []

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

        # Get all adjacent vertices of the dequeued vertex
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return traversal_order

# --- Example Usage ---
# Build a graph
edges = [
    ('A', 'B'), ('A', 'C'),
    ('B', 'D'), ('B', 'E'),
    ('C', 'F'), ('E', 'F')
]
adj = defaultdict(list)
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u) # For an undirected graph

# Perform BFS starting from node 'A'
bfs_path = bfs(adj, 'A')
print(f"BFS Traversal Order: {bfs_path}")

# Expected output might be: ['A', 'B', 'C', 'D', 'E', 'F']
# The exact order of nodes at the same level (e.g., B and C)
# depends on the order they were added to the adjacency list.

This image connects the code you just saw with a visualization of the data structures involved.

Application: Shortest Path and Distance

The most powerful application of BFS is finding the shortest path in an unweighted graph. We can easily augment our BFS function to calculate the distance (number of edges) from the source to all other nodes.

We do this by storing the level of each node. The source node is at level 0. Any neighbor of the source is at level 1. Any unvisited neighbor of a node at level k will be at level k+1.

Let's see how to implement this, and also how to find the actual path.

Here's how you can modify the BFS function to return the distances and parent pointers:

def bfs_shortest_path(graph, start_node):
    visited = {start_node}
    queue = deque([(start_node, 0)]) # Queue now stores (node, level)
    
    levels = {start_node: 0}
    parents = {start_node: None}

    while queue:
        node, level = queue.popleft()

        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                parents[neighbor] = node
                levels[neighbor] = level + 1
                queue.append((neighbor, level + 1))
    
    return levels, parents

# Using the same graph as before
levels, parents = bfs_shortest_path(adj, 'A')

# Find shortest distance to node 'F'
print(f"Shortest distance from A to F: {levels['F']}")

# Reconstruct the path from A to F
path = []
curr = 'F'
while curr is not None:
    path.append(curr)
    curr = parents[curr]
path.reverse() # The path is built backwards, so reverse it
print(f"Shortest path from A to F: {path}")

Output:

Shortest distance from A to F: 2
Shortest path from A to F: ['A', 'C', 'F']

This ability to find not just the distance but the path itself is a fundamental technique in your competitive programming toolkit.

graph = {
    0: [1, 3],
    1: [0, 2],
    2: [1, 5],
    3: [0, 4],
    4: [3, 5],
    5: [2, 4]
}

Complexity Analysis

Just like DFS, the complexity of BFS is proportional to the number of vertices and edges in the graph.

• Time Complexity: $O(V+E)$, where $V$ is the number of vertices and $E$ is the number of edges. This is because every vertex is enqueued and dequeued exactly once, and every edge is considered once.
• Space Complexity: $O(V)$. In the worst-case scenario (a "star" graph where one central node is connected to all others), the queue could hold up to $V-1$ vertices at one time. The visited set also contributes to this space complexity.

Conclusion

You've now added Breadth-First Search to your algorithmic arsenal, a powerful technique for exploring graphs and a go-to method for shortest path problems on unweighted graphs.

Key Takeaways:

• BFS explores a graph level by level, starting from a source node.
• It uses a queue (FIFO) to manage the order of nodes to visit.
• BFS is guaranteed to find the shortest path in terms of the number of edges in an unweighted graph.
• By tracking levels and parents, you can find both the shortest distance and reconstruct the path itself.
• The time and space complexities are $O(V+E)$ and $O(V)$ respectively, the same as DFS.

Up Next:
In the following lessons, we'll start applying these traversal algorithms to solve more complex problems. Our next topic will be detecting cycles in graphs using DFS, which is a classic application of the depth-first traversal pattern.