Lesson 16 · Data structures

Graphs

A graph is a set of things (vertices) joined by connections (edges). Road maps, social networks, the web and the internet's routers are all graphs. Drive a little car around six towns to see edges, paths, cycles and connected components, then watch the same map stored two ways, as an adjacency list and as an adjacency matrix, and see what each costs in memory.

10 min11 steps5 questionsBeginner

Fig 16 · Interactive

Loading figure…

or ← →

Check yourself

5 quick questions

Pick an answer to see why. Your score saves with your progress.

01A graph has 4 vertices and 3 undirected edges. How many cells does its adjacency matrix have?

A matrix has one row and one column per vertex, so 4 × 4 = 16 cells, no matter how many edges there are.

02In the same graph, how many entries does the adjacency list hold in total?

Each undirected edge appears twice, once in the list of each end, so 3 edges give 6 entries.

03Road X → Y is one-way. In the adjacency matrix, what is true?

A directed edge only goes one way, so only the cell from X to Y is set. That is why a directed graph's matrix need not be symmetric.

04Which of these is a cycle?

A cycle follows edges and comes back to where it started without reusing an edge.

05What makes a graph a tree?

A tree is a connected graph with no cycles, so there is exactly one path between any two vertices. A tree with V vertices has V − 1 edges.

Key terms

Glossary

Graph: A set of vertices together with edges that join pairs of them.
Vertex (node): One of the things in a graph, such as a town, a person, a web page or a router.
Edge: A connection between two vertices, such as a road. Undirected edges work both ways; directed edges go one way.
Weighted edge: An edge that carries a number, such as a road's length in km.
Adjacency list: For each vertex, a list of its neighbours. Its size grows with the number of edges.
Adjacency matrix: A grid with a row and a column per vertex; a cell says whether (or how strongly) two vertices are joined. It always has V × V cells.
Path and cycle: A path is a route along edges; a cycle is a path that ends where it started without reusing an edge.
Connected component: A group of vertices that can all reach one another along edges, and nothing else.

Fine print

Notes and sources

The towns, roads and distances are a made-up example, kept small so the whole matrix fits on one card.
For V vertices and E edges, an adjacency matrix always has V × V cells, while an adjacency list holds 2E entries for an undirected graph (E for a directed one), plus one list per vertex.
Checking whether two vertices are joined takes one look in a matrix (m[1][2]); with a list you search one vertex's neighbours, which is quick when a vertex has few of them.
A tree with V vertices always has exactly V − 1 edges. The whole map, with E and F apart, is a forest: a graph with no cycles made of separate trees.
With weights, "no road" cannot be written as 0 (a road could have length 0), so programs mark it with a special value such as None or infinity; the card shows –.

Quiz Unlocks after the last step.