City graph
- Algorithms course
- Intermediate
- Lesson 74/80
- 4 min
Define cities as an adjacency list.
City graph
We defined cities with an adjacency list. Now we will write a function that adds a new neighbor to a city.
This lets us grow the graph dynamically; new links can be added.
Adding a neighbor uses append on the list; simple but important.
Graph modification
Adding a neighbor to a city means appending to that city's list. The graph object changes in place.
This makes graph sharing easy; it updates via reference.
Note: in an undirected graph both cities' lists need updating; here we add one side.
Practice Add neighbor
Write add_neighbor(graph, city, neighbor). Append the neighbor to the city's list and return the graph. Print {'A': ['B', 'C', 'E'], ...} with print(add_neighbor(build_cities(), "A", "E")).
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 neighborSample 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
print(add_neighbor(build_cities(), "A", "E"))Expected output
{'A': ['B', 'C', 'E'], '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 How is a new neighbor added to the adjacency list?
- With append Correct answer
- With pop
- With remove
- With sort
Explanation: With append.
2 Append call
graph[city].____(neighbor)graph[city].append(neighbor)Explanation: append is right.
3 City graph: match the terms
| Term | Meaning |
|---|---|
append |
Add back |
graph |
Cities |
neighbor |
Neighbor |
in-place |
In place |