Pointer Walk

Graphs

Things and the connections between them. Two ways to store the same graph, and what each one makes fast.

Data StructuresBeginner9 min read

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

KindMeaningExample
UndirectedA connection works both waysFriendship: if A is B's friend, B is A's
DirectedA connection has a directionFollowing: A follows B, B may not follow A
WeightedEach connection has a numberA road with a distance or a toll
CyclicYou can go round in a loopMost road maps
AcyclicNo loopsTasks 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.

One graph, two ways to store itInteractive
ABCDE

Adjacency list

A:
B:
C:
D:
E:

Adjacency matrix

ABCDE
A00000
B00000
C00000
D00000
E00000

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.

python
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 listAdjacency matrix
MemoryOne entry per connectionOne cell per pair of nodes
Is A connected to B?Scan A's listOne lookup
List all of A's neighboursRead A's listScan a whole row
Add a nodeAdd one entryGrow the whole grid
Best whenFew connections per nodeAlmost 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.

Your progress

Check your progress

0%

  1. Read the page50% of this page

    When you have gone through the page and its animations, tick it off.

  2. Take the quiz50% of this page

    7 questions, from easy to hard. Take it as often as you like: the questions change, and only your best score counts.

Saved on this device only. See all your progress