Breadth First Search (BFS)

Definition

BFS is a traversal algorithm that explores the graph level by level. It visits all immediate neighbors of a starting node before moving on to the neighbors’ neighbors.

How it Works

1. Start at a node and add it to a Queue.
2. While the queue is not empty:

• Remove the first node.
• Mark it as visited.
• Add all its unvisited neighbors to the back of the queue.

Real-World Analogy

Ripples in Water: When you drop a stone in a pond, the waves spread out in concentric circles. First, the water closest to the stone moves, then the water a bit further out, and so on.

Code Example (Python)

from collections import deque

def bfs(graph, start_node):
    visited = set()
    queue = deque([start_node])
    visited.add(start_node)

    while queue:
        node = queue.popleft() # Dequeue
        print(node, end=" ")   # Process
       
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor) # Enqueue

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [], 'E': [], 'F': []
}

print("BFS Traversal:")
bfs(graph, 'A')
# Output: A B C D E F (Notice it explores 'C' before deep 'D')

Complexity & Use Cases

• Time: O(V + E).
• Space: O(V) – For the queue.
• Use Cases: Finding the shortest path in an unweighted graph, GPS navigation (nearby places), social network “friends of friends.”