City graph

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.

Exercise 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")).

Show example 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"))

Test yourself

How is a new neighbor added to the adjacency list?
- With append
- With pop
- With remove
- With sort
Show answer

With append — With append.

Append call

graph[city].____(neighbor)

Show answer

graph[city].append(neighbor)

City graph: match the terms

append

Add back
graph

Cities
neighbor

Neighbor
in-place

In place

Next lesson: BFS for reachability

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies