Mastering Algorithms - Breadth-First Search

What is Breadth-First Search?

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. Its implementation is straightforward: maintain a queue, a visited set, and a loop that continues until the queue is empty, processing nodes and neighbors in the order they are discovered.

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. The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges, as each vertex and edge is visited once. The space complexity is O(V), as it requires storage for the queue and the visited set. BFS works for both directed and undirected graphs and can be adapted to weighted graphs when combined with other algorithms like Dijkstra's. Its simplicity and effectiveness makes it a fundamental algorithm in computer science and graph theory.

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)

Common Trends in Graph Problems where BFS is Applied

Level-by-Level Processing: BFS naturally processes nodes level by level, making it ideal for problems that require exploring all nodes at a certain distance before moving to the next level.
Shortest Path Guarantee: In unweighted graphs, BFS guarantees finding the shortest path (in terms of number of edges) from the source to any reachable node.
Queue-Based Traversal: The queue data structure ensures nodes are processed in the order they were discovered, maintaining the breadth-first property.
Distance Tracking: Often used to track distances or levels from a starting node, which is useful for problems like finding minimum steps or levels in a tree/graph.
Layer-by-Layer Exploration: Perfect for problems requiring exploration of all neighbors at the current level before moving deeper, such as level-order tree traversal or social network degree analysis.

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.

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