Storing a Graph
Adjacency lists.
To work with a graph in code, we need to store which nodes are connected. The most common way is an adjacency list. For every node, keep a list of its neighbours.

- Store the connections
- For every node
- A list of its neighbours
A friendship graph
A dictionary is perfect. Each person maps to the list of their friends. Because friendship goes both ways, Ana lists Ben, and Ben lists Ana. Getting someone's friends is one lookup. Run it. We print each person, and how many friends they have.
friends = {
"Ana": ["Ben", "Cara"],
"Ben": ["Ana", "Dev"],
"Cara": ["Ana", "Dev", "Eli"],
"Dev": ["Ben", "Cara", "Fay"],
"Eli": ["Cara"],
"Fay": ["Dev"],
}
for person, fs in friends.items():
print(f"{person:<5} {len(fs)} friends: {', '.join(fs)}")Ana 2 friends: Ben, Cara Ben 2 friends: Ana, Dev Cara 3 friends: Ana, Dev, Eli Dev 3 friends: Ben, Cara, Fay Eli 1 friends: Cara Fay 1 friends: Dev
Lists or a matrix?
The other option is an adjacency matrix, a grid with a row and a column for every node, and a one where they're connected. A matrix answers, are these two connected, in O of one, but uses N squared memory. Most real graphs are sparse, with few connections each, so adjacency lists are usually the better choice.
| key | value |
|---|---|
| Adjacency list | dict of neighbour lists |
| Memory | O(nodes + edges) |
| Matrix | n × n grid |
| Usually | lists win |
Summary
An adjacency list maps each node to its neighbours. In Python, that's a dictionary of lists. Next, exploring a graph, breadth first.
Key takeaways- dict of lists
- Neighbours in O(1)
- Lists for sparse graphs