Breadth-First Search (BFS)

Breadth-First Search (BFS) is a graph traversal algorithm that explores all nodes at the present “depth” level before moving on to nodes at the next level. BFS is commonly used for finding the shortest path in unweighted graphs, as it explores each layer fully before moving to the next.

BFS can be implemented using an iterative approach with a queue to manage nodes, making it both simple and efficient.

How BFS Works

BFS starts from a source node and explores all its neighboring nodes before moving to their neighbors. This breadth-first expansion ensures that BFS explores the shallowest nodes (closest to the starting point) first.

Key Properties of BFS:

• Time Complexity: O(V + E), where V is the number of vertices and E is the number of edges. Each node and edge is processed once.
• Space Complexity: O(V), due to the storage of the queue and visited set.
• Traversal Order: BFS traverses nodes in a breadth-first manner, processing all nodes at a certain distance from the starting node before moving to the next level.

Use Cases of BFS:

• Shortest Path in Unweighted Graphs: BFS guarantees the shortest path in terms of the number of edges for unweighted graphs.
• Connected Components: In undirected graphs, BFS can help identify all nodes connected to a given node.
• Cycle Detection: BFS can detect cycles in undirected graphs.
• Level Order Traversal: BFS is used in binary trees to perform level order traversal.

Graph Representation for BFS

Graphs are typically represented as:

• Adjacency List: A dictionary where each node has a list of adjacent nodes.
• Adjacency Matrix: A 2D array where an entry at [i][j] indicates an edge between nodes i and j.

We’ll use an adjacency list representation in this example for simplicity and efficiency.

BFS Implementation

BFS is implemented iteratively using a queue to manage nodes in the current level. Nodes are processed level-by-level, which makes the queue an ideal structure for this approach.

Code Example for BFS

from typing import Dict, List
from collections import deque

def bfs(graph: Dict[int, List[int]], start: int) -> None:
    """
    Perform BFS on a graph from a starting node.
    - graph: Dictionary representing an adjacency list of the graph
    - start: The starting node for BFS traversal
    """
    visited = set()            # To track visited nodes
    queue = deque([start])      # Queue to manage nodes to explore
    while queue:
        node = queue.popleft()  # Dequeue the next node
        
        if node not in visited:
            visited.add(node)
            print(f"Visited {node}")
            # Enqueue all unvisited neighbors
            for neighbor in graph[node]:
                if neighbor not in visited:
                    queue.append(neighbor)

Example Usage:

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

bfs(graph, 0)

Explanation of Code:

1. Queue Initialization: The start node is added to the queue.

2. Processing Nodes: Each node is dequeued, marked as visited, and its neighbors are added to the queue if they haven’t been visited.

3. Order of Traversal: BFS visits nodes layer-by-layer, processing all nodes connected to the current layer before moving to deeper nodes.

Common Variations of BFS

Shortest Path Calculation (in Unweighted Graphs): BFS can be modified to calculate the shortest path from a starting node to each reachable node by maintaining a dictionary of distances from the start node.

def bfs_shortest_path(graph: Dict[int, List[int]], start: int) -> Dict[int, int]:
    """
    Find the shortest path in an unweighted graph from the start node.
    - graph: Dictionary representing an adjacency list of the graph
    - start: The starting node
    Returns a dictionary with nodes as keys and their distances from the start node as values.
    """
    distances = {start: 0}      # Distance from start node to itself is 0
    queue = deque([start])      # Queue to manage nodes to explore
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in distances:  # Not visited
                distances[neighbor] = distances[node] + 1
                queue.append(neighbor)
    return distances

Level Order Traversal(for Trees): BFS is commonly used for level order traversalin binary trees, where each level is processed in order.

Applications of BFS

1. Shortest Path in Unweighted Graphs: BFS is ideal for finding the shortest path in unweighted graphs, where the shortest path is defined by the minimum number of edges.
2. Connected Components: BFS can identify all nodes in the same connected component as the starting node in an undirected graph.
3. Cycle Detection: In undirected graphs, BFS can detect cycles by checking for visited nodes. If a visited node is encountered that isn’t the parent of the current node, a cycle exists.
4. Level Order Traversal: BFS is used in binary trees for level order traversal, processing each level one at a time.
5. Flood Fill Algorithms: BFS is often used in flood fill algorithms (e.g., to fill connected regions in images or grids).