Mastering Algorithms

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(node):
    queue = [node]
    visited = set()
    while queue is not empty:
        current = queue.dequeue()
        mark current as visited
        for each neighbor in current.children:
            if neighbor is not visited:
                queue.enqueue(neighbor)

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):
    if start == target:
        return [start]
    
    queue = deque([(start, [start])])
    visited = {start}
    
    while queue:
        node, path = queue.popleft()
        
        for neighbor in graph[node]:
            if neighbor == target:
                return path + [neighbor]
            
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append((neighbor, path + [neighbor]))
    
    return None  # No path found

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

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = [root]
        
        while queue:
            level_size = len(queue)
            current_level = []
            
            for _ in range(level_size):
                node = queue.pop(0)
                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: