Project: Overview
- Algorithms course
- Intermediate
- Lesson 73/80
- 4 min
Plan a mini app that finds shortest city links.
Project: Overview
In this project you will build a mini app that finds reachable cities with BFS on a city map.
First define the city graph, then add a neighbor, then compute reachability with BFS and print it.
Each lesson adds a piece with a code step; the initial code includes the previous lesson's solution.
City graph
We will define cities with an adjacency list: each city holds its neighbors in a list.
This structure suits BFS and DFS; it gives fast access to neighbors.
Our city graph: A—B, A—C, B—D, C—D links join four cities.
Practice Define the city graph
Write build_cities(). Return the city graph as an adjacency list. Print {'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']} with print(build_cities()).
Starter code
def build_cities():
# Define the city graphSample solution
def build_cities():
# Define the city graph
return {"A": ["B", "C"], "B": ["A", "D"], "C": ["A", "D"], "D": ["B", "C"]}
print(build_cities())Expected output
{'A': ['B', 'C'], 'B': ['A', 'D'], 'C': ['A', 'D'], 'D': ['B', 'C']}
Questions and answers
Review the lesson questions together with their answers. To test yourself, solve the lesson interactively.
1 Project: Overview: match the terms
| Term | Meaning |
|---|---|
graph |
City map |
BFS |
Reachability |
city |
Vertex |
neighbor |
Neighbor |
2 Which algorithm will this project use?
- DFS
- BFS Correct answer
- Dijkstra
- Greedy
Explanation: BFS.
3 City definition
return {"A": ____}return {"A": ["B", "C"]}Explanation: ["B", "C"] is right.