POV: You're Lost in the Mall (BFS Explained)

POV: You're Lost in the Mall (BFS Explained)

Imagine trying to find a single store in a large mall without a map. Instead of wandering randomly, you check every store on the current floor before moving to the next level. This systematic approach mirrors the Breadth-First Search (BFS) algorithm, which explores nodes level by level to find the shortest path or target efficiently.

Code

from collections import deque

def bfs_find_store(mall_map, start_floor, target_store):
  """
  mall_map: dict mapping floor numbers to lists of stores on that floor
  start_floor: the floor number where the search begins
  target_store: the store we want to find
  """
  visited_floors = set()
  queue = deque([start_floor])  # floors to explore

  while queue:
    current_floor = queue.popleft()
    if current_floor in visited_floors:
      continue
    visited_floors.add(current_floor)

    print(f"Checking floor {current_floor}...")

    # Check all stores on this floor
    for store in mall_map.get(current_floor, []):
      if store == target_store:
        return f"Found {target_store} on floor {current_floor}!"

    # Add adjacent floors to the queue (up and down)
    if current_floor + 1 in mall_map:
      queue.append(current_floor + 1)
    if current_floor - 1 in mall_map:
      queue.append(current_floor - 1)

  return f"{target_store} not found in the mall."

# Example mall layout
mall = {
  1: ["Shoe Store", "Clothing", "Food Court"],
  2: ["Candle Shop", "TechByte", "Bookstore"],
  3: ["Cinema", "Arcade"]
}

print(bfs_find_store(mall, start_floor=1, target_store="TechByte") )

Key Points

• Breadth-First Search explores neighbors (floors) level by level before going deeper.
• It uses a queue to keep track of which nodes (floors) to visit next.
• BFS guarantees finding the shortest path or closest target in an unweighted graph.
• In this analogy, floors represent nodes and stores are checked before moving to adjacent floors.
• Marking visited floors prevents revisiting and infinite loops.