AI Hints
DSA in Python · Lesson 77 of 132

Storing a Graph

Adjacency lists.

⏱ 2 min read▶ Video at 1:30:59🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

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.

Storing a Graph
From the video: Storing a Graph
  • 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.

graph.pypython
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)}")
Output
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.

keyvalue
Adjacency listdict of neighbour lists
MemoryO(nodes + edges)
Matrixn × n grid
Usuallylists 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
Next up: Breadth First Search — exploring in rings