Breadth-First Search

What is Breadth-First Search?

Breadth-First Search (BFS) is a graph traversal algorithm that explores a graph level by level, starting from a given node. It uses a queue (FIFO - First In, First Out) to ensure all nodes at the current level are visited before moving to the next level. BFS is particularly useful for finding the shortest path in unweighted graphs. Note: Edge weights are ignored by BFS - it treats all edges as having weight 1, finding the path with the minimum number of edges.

How It Works

BFS explores the graph level by level, ensuring all nodes at distance k are visited before nodes at distance k+1:

1. Start with the source node, mark it as level 0, and add it to the queue
2. Dequeue a node from the front of the queue
3. Visit all unvisited neighbors of the current node
4. Mark neighbors as visited, set their level to current level + 1, and add them to the queue
5. Repeat until the queue is empty

Implementation

Here's a Python implementation using a queue:

from typing import Dict, List
from collections import deque

def bfs(graph: Dict[str, List[str]], start: str) -> Dict[str, int]:
    """
    Perform Breadth-First Search to find the minimum number of edges (levels) 
    from start node to all reachable nodes in an unweighted graph.
    
    BFS explores the graph level by level, ensuring all nodes at distance k
    are visited before nodes at distance k+1. This guarantees finding the
    shortest path in terms of number of edges.
    
    Args:
        graph: Adjacency list representation. Each node maps to a list of neighbors.
        start: Starting node identifier.
    
    Returns:
        Dictionary mapping each node to its level (minimum edges from start).
        Unreachable nodes will have level float('inf').
    
    Time Complexity: O(V + E) where V is vertices and E is edges.
    Space Complexity: O(V) for queue and visited set.
    """
    levels: Dict[str, int] = {node: float('inf') for node in graph}
    levels[start] = 0
    queue: deque[str] = deque([start])
    visited: set[str] = {start}
    
    while queue:
        current = queue.popleft()
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                levels[neighbor] = levels[current] + 1
                queue.append(neighbor)
    
    return levels

# Example
graph = {'A': ['B', 'C', 'E'], 'B': ['C', 'A'],
         'C': ['D', 'E', 'A', 'B'], 'D': ['C', 'E'], 'E': ['A', 'C', 'D']}
print(bfs(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 1, 'D': 2, 'E': 1}

Time Complexity

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges. Each vertex is visited once, and each edge is examined once. This makes BFS very efficient for graph traversal and finding shortest paths in unweighted graphs.

Edge Cases: If the graph contains disconnected components, BFS will only explore nodes reachable from the start node. Unreachable nodes will be marked as such in the visualization.

Real-World Applications

• Shortest path finding: finding the minimum number of edges between two nodes in unweighted graphs
• Social networks: finding degrees of separation between users
• Web crawling: exploring websites level by level
• Puzzle solving: finding minimum moves in games like Rubik's cube
• Network broadcasting: efficiently broadcasting messages in networks
• Connected components: finding all nodes reachable from a starting node