Things and connections
A list has an order. A tree has a hierarchy. Many real problems have neither. They are just things with connections between them.
- Cities, and the roads between them.
- People, and who is friends with whom.
- Web pages, and the links between them.
- Tasks, and which must be finished before which.
The structure for this is a graph. The things are called nodes (or vertices) and the connections are called edges.
A tree is a special kind of graph, one with no loops and a single root. A graph has no such restrictions: any node can connect to any other, and following connections can lead you back to where you started.
Kinds of graph
| Kind | Meaning | Example |
|---|---|---|
| Undirected | A connection works both ways | Friendship: if A is B's friend, B is A's |
| Directed | A connection has a direction | Following: A follows B, B may not follow A |
| Weighted | Each connection has a number | A road with a distance or a toll |
| Cyclic | You can go round in a loop | Most road maps |
| Acyclic | No loops | Tasks that depend on earlier tasks |
How do you store one?
A picture is fine for people. A program needs the connections in a form it can look up. There are two standard choices.
Adjacency list
Adjacency matrix
Start. Five things, called nodes. Think of five people, five cities or five web pages. Nothing connects them yet.
- Nodes
- 5
- Connections
- 0
- Grid cells
- 25, of which 0 are 1
Adjacency list
For each node, keep a list of the nodes it connects to.
graph = {
"A": ["B", "C"],
"B": ["A", "D"],
"C": ["A", "D"],
"D": ["B", "C", "E"],
"E": ["D"],
}It stores only the connections that exist. "Who are D's neighbours?" is answered by reading one list.
Adjacency matrix
Make a grid with a row and a column for every node. Put a 1 where two nodes are connected and a 0 where they are not.
It answers "are A and D connected?" in one step: look at one cell. But the grid has a cell for every possible pair, whether connected or not.
Which one to use
| Adjacency list | Adjacency matrix | |
|---|---|---|
| Memory | One entry per connection | One cell per pair of nodes |
| Is A connected to B? | Scan A's list | One lookup |
| List all of A's neighbours | Read A's list | Scan a whole row |
| Add a node | Add one entry | Grow the whole grid |
| Best when | Few connections per node | Almost everything is connected |
Example
A million people
A social network has a million users with about 200 friends each.
As adjacency lists: a million lists of 200 entries. 200 million entries.
As a matrix: a million rows by a million columns. A trillion cells, nearly all of them 0.
Most real graphs are like this, with far fewer connections than there could be. So the adjacency list is the usual choice.
For a weighted graph, store the weight alongside: "A": [("B", 5), ("C", 2)] in a list, or the weight itself in the matrix cell.
What you do with a graph
Storing it is only the start. Most graph problems are one of a few questions.
- Can I get from here to there? Visit everything reachable from a starting node. See Graph Traversal: BFS and DFS.
- What is the shortest or cheapest route? See Pathfinding.
- Which nodes belong together? Find the separate connected groups. See Union-Find.
- In what order should these be done? For tasks with dependencies, find an order where everything comes after what it needs. This is a topological sort, and it is how build tools and package installers decide what to do first.
Spotting a graph problem
Problems rarely say "this is a graph". Look for things with relationships:
- A grid or maze: each cell is a node, connected to its neighbours.
- "Transform one word into another by changing one letter at a time": words are nodes, connected if they differ by one letter.
- Course prerequisites: courses are nodes, with an edge from each course to the ones that require it.
- Flights, pipes, wires, friendships, references between files.
Once you see the nodes and edges, the standard algorithms apply.
Key takeaways
- A graph is a set of nodes and the edges that connect them.
- Edges can be one-way or two-way, and can carry a weight.
- An adjacency list stores each node's neighbours. It is compact and suits most graphs.
- An adjacency matrix has a cell for every pair. It answers "are these two connected?" instantly and uses far more memory.
- Many problems become easy once you recognise the nodes and edges in them.