Paul's Python CoursePPC

Graphs as dictionaries of neighbours

Not met yet

A graph is a set of places, called nodes, and the connections between them, called edges: towns and roads, people and friendships, parts and the parts they fit. The usual way to keep one in Python is a dictionary of neighbours: each place, and a list of the places one step away. A two-way road is written in both lists; written in only one, it's one way. A place with no list of its own has nothing leading out of it, so roads.get(place, []) is safer than roads[place].

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks writing a road in one place's list of neighbours makes it go both ways.
  • Thinks every place in a dictionary of neighbours has its own key, missing places that only appear in other places' lists.
  • Thinks a graph needs positions or a drawing, rather than only the places and which ones are connected.

Where it comes up