BFS for reachability
- Algorithms course
- Intermediate
- Lesson 75/80
- 4 min
Find reachable cities with BFS.
BFS for reachability
Now we will find which cities are reachable from a city with BFS. Discover all reachable cities.
BFS works with a queue and a visited set; it spreads layer by layer.
We will return the sorted list of reachable cities; the output is deterministic.
Sorted output
We sort results with sorted() for deterministic output; every run gives the same result.
BFS output is already deterministic but sorting adds a guarantee; this matters for testing.
The sorted list makes output readable; cities appear in alphabetical order.
Practice Reachable cities
Write bfs_reachable(graph, start). Return the sorted list of cities reachable via BFS. Print ['A', 'B', 'C', 'D'] with print(bfs_reachable(build_cities(), "A")).
Starter code
def build_cities():
# Define the city graph
return {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
def add_neighbor(graph, city, neighbor):
# Add neighbor
graph[city].append(neighbor)
return graph
def bfs_reachable(graph, start):
# Reachable citiesSample solution
def build_cities():
# Define the city graph
return {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
def add_neighbor(graph, city, neighbor):
# Add neighbor
graph[city].append(neighbor)
return graph
def bfs_reachable(graph, start):
# Reachable cities
visited = set()
queue = [start]
while queue:
node = queue.pop(0)
if node not in visited:
visited.add(node)
for nb in graph[node]:
if nb not in visited:
queue.append(nb)
return sorted(visited)
print(bfs_reachable(build_cities(), "A"))Expected output
['A', 'B', 'C', 'D']
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Queue init
queue = [____]queue = [start]Explanation: start is right.
2 BFS for reachability: match the terms
| Term | Meaning |
|---|---|
BFS |
Layer |
queue |
Queue |
visited |
No repeat |
sorted |
Alphabetical |
3 What does sorting BFS output ensure?
- Faster execution
- Deterministic result Correct answer
- Fewer edges
- Less memory
Explanation: Deterministic result.