BFS traversal and applications in Data Structures Theory - Mini Project: Build & Apply

BFS Traversal and Applications

📖 Scenario: Imagine you are exploring a city with many connected streets and intersections. You want to visit all places starting from your home, moving step-by-step to the nearest unvisited places first.

🎯 Goal: You will build a simple representation of a city map as a graph, set up a starting point, perform a Breadth-First Search (BFS) traversal to visit all connected places, and finally identify the order in which places are visited.

📋 What You'll Learn

Create a graph using a dictionary where keys are place names and values are lists of connected places.

Set a starting place for BFS traversal.

Implement BFS traversal using a queue to visit places level by level.

Record the order of places visited during BFS.

💡 Why This Matters

🌍 Real World

BFS is used in real life to explore networks like social connections, city maps, or computer networks to find the shortest path or to visit all connected nodes.

💼 Career

Understanding BFS is important for roles in software development, data analysis, and network engineering where graph traversal and search algorithms are common.

1

Create the city map graph

Create a dictionary called city_map with these exact entries: 'Home': ['Park', 'Mall'], 'Park': ['Home', 'School'], 'Mall': ['Home', 'Cinema'], 'School': ['Park'], 'Cinema': ['Mall'].

Data Structures Theory

# Create the city_map dictionary with the specified connections
# Your code here

Need a hint?

Think of city_map as a dictionary where each place points to a list of places directly connected to it.

2

Set the starting place for BFS

Create a variable called start_place and set it to the string 'Home'.

Data Structures Theory

city_map = {
    'Home': ['Park', 'Mall'],
    'Park': ['Home', 'School'],
    'Mall': ['Home', 'Cinema'],
    'School': ['Park'],
    'Cinema': ['Mall']
}

# Set the starting place for BFS traversal
# Your code here

Need a hint?

The BFS traversal needs a starting point. Use the exact variable name start_place and assign it the string 'Home'.

3

Implement BFS traversal

Write code to perform BFS traversal starting from start_place. Create a list called visited to record visited places, a list called queue initialized with start_place, and use a while loop to visit places. In each loop, remove the first place from queue, add it to visited, then add its unvisited neighbors from city_map to queue.

Data Structures Theory

city_map = {
    'Home': ['Park', 'Mall'],
    'Park': ['Home', 'School'],
    'Mall': ['Home', 'Cinema'],
    'School': ['Park'],
    'Cinema': ['Mall']
}

start_place = 'Home'

# Implement BFS traversal to visit all connected places
# Your code here

Need a hint?

Use a queue (list) to keep track of places to visit next. Always visit the first place in the queue, mark it visited, then add its neighbors if not visited.

4

Record and finalize BFS visit order

Ensure the list visited contains the order of places visited by BFS starting from start_place. This list represents the BFS traversal order of the city map.

Data Structures Theory

city_map = {
    'Home': ['Park', 'Mall'],
    'Park': ['Home', 'School'],
    'Mall': ['Home', 'Cinema'],
    'School': ['Park'],
    'Cinema': ['Mall']
}

start_place = 'Home'

visited = []
queue = [start_place]

while queue:
    current_place = queue.pop(0)
    if current_place not in visited:
        visited.append(current_place)
        for neighbor in city_map[current_place]:
            if neighbor not in visited and neighbor not in queue:
                queue.append(neighbor)

# The BFS traversal order is now stored in visited
# Your code here

Need a hint?

The visited list holds the order in which places were visited by BFS. This completes the BFS traversal.