Breadth First Search (BFS) for Graphs

# CHAPTER 21

Breadth First Search (BFS) for Graphs #

1. Introduction #

2. Learning Objectives #

• Trace the step-by-step Queue state during a Graph BFS.

• Understand how BFS mechanically guarantees the Shortest Unweighted Path.

• Implement an array to track the exact "Distance" from the starting node.

• Write a production-ready Graph BFS algorithm in Python and Java.

3. The BFS Radar (Concentric Rings) #

• Level 0: Node A (Distance = 0)

• Level 1: All immediate neighbors of A. (Distance = 1)

• Level 2: All neighbors of Level 1. (Distance = 2)

Because the FIFO Queue strictly prevents Level 2 from being evaluated until Level 1 is completely empty, the physical moment the algorithm collides with the target node, it has *mathematically proven* that there is no shorter route. If there were a shorter route, it would have been found in a previous concentric ring!

4. Tracking the Shortest Path (Distance Array) #

The Logic: When Node X dequeues and finds an unvisited neighbor Node Y:

1. 1. Mark Y as Visited.

1. 2. Calculate: Distance[Y] = Distance[X] + 1

1. 3. Enqueue Y.

Visual Trace: Graph: A - B - C (A connects to B, B connects to C). Start at A.

• Dist[A] = 0. Enqueue A.

• Dequeue A. Neighbor is B. Dist[B] = Dist[A] + 1 = 1. Enqueue B.

• Dequeue B. Neighbor is C. Dist[C] = Dist[B] + 1 = 2. Enqueue C.

5. Code Execution (Python) #

from collections import deque

def bfs_shortest_path(graph, start_node):
    visited = set([start_node]) # Cache
    queue = deque([start_node]) # FIFO Queue
    
    # Track distances
    distances = {node: float('inf') for node in graph}
    distances[start_node] = 0
    
    while queue:
        current = queue.popleft() # Dequeue
        print(f"Evaluating {current} at distance {distances[current]}")
        
        for neighbor in graph[current]:
            if neighbor not in visited:
                visited.add(neighbor)
                
                # The critical Distance calculation!
                distances[neighbor] = distances[current] + 1 
                
                queue.append(neighbor) # Enqueue
                
    return distances

# Adjacency List
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D'],
    'C': ['A', 'D'],
    'D': ['B', 'C', 'E'],
    'E': ['D']
}

print(bfs_shortest_path(graph, 'A'))

6. Applications of Graph BFS #

• Peer-to-Peer Networks: BitTorrent uses BFS to find the closest neighboring computers to download file fragments.

• Web Crawlers: Google Search crawlers use BFS to index the web. They start at a popular page (Level 0), grab all links on that page (Level 1), and then process those links before diving deeper, preventing the crawler from getting permanently lost in a deep spam-site loop.

• Social Networks: Finding "Mutual Friends" and calculating "Degrees of Separation" relies purely on BFS concentric mapping.

7. Complexity Analysis #

• Time Complexity: $O(V + E)$. The Queue ensures every Vertex is popped once, and the inner for loop checks every connected Edge.

• Space Complexity: $O(V)$. The Queue, the Visited Set, and the Distance Array all scale linearly with the number of Vertices.

8. Common Mistakes #

• Forgetting to Enqueue Disconnected Nodes: Just like DFS, a raw BFS algorithm will stop when the local island is mapped. You must wrap the BFS call in a for node in allnodes: loop if you are attempting to map a fractured, multi-island network matrix.

11. Interview Preparation #

• *Algorithmic Routing:* "A Knight is placed on a standard Chessboard. What is the absolute minimum number of moves required to reach the opposing King?" *(Answer: Do not attempt to mathematically calculate geometric angles! Treat the 64 squares as Graph Vertices. Treat the L-shaped legal moves as Edges. Launch an instant BFS search from the Knight's coordinate, and the first time it collides with the King, you mathematically have the minimum move count!)*

12. Summary #

13. Next Chapter Recommendation #