Graphs

Python · Unit 24: Data structures

A graph is a bunch of connected things: friends, subway stations, pages with links.

You keep it in a dictionary: each name with the list of who it reaches. Nothing else is needed.

routes = {
    "Amy": ["Leo", "Sam"],
    "Leo": ["Amy"],
    "Sam": [],
}
print(routes["Amy"])

Prints

['Leo', 'Sam']

The rest of the explanation is in the lesson, which is part of the full plan.

Exercises in this lesson

You do them in the app, which checks them on the spot and explains why.

1. Predict the output
What does this code print?
2. Complete the code
Connect B back to A too. It should print: ['A']
3. Multiple choice
In links = {"A": ["B"], "C": []}, what does C's empty list mean?
4. Put the lines in order
Put connect(g, a, b) together; it adds b as a neighbor of a even when a is new to the graph.
5. Predict the output
Now B and C both lead to D. What does it print?
6. Find the bug
It should visit A's two neighbors first and D at the very end. Which line has the error?
7. Complete the code
B leads back to A. Complete it so nobody is visited twice. It should print A, B and C.
8. Find the case that fails
neighbors(g, who) should return the list of neighbors, or [] if that person isn't in the graph. Which call breaks it?
9. Predict the output
dist keeps how many steps away each node ended up. What does it print?

It opens in your browser. This lesson is part of the full plan; the first unit of each course is free.