Graphs and How to Store Them
Nodes joined by edges, with the edges possibly directed and possibly carrying a weight. The same graph can be held as an adjacency matrix or as an adjacency list, and the choice decides which questions are cheap to ask.
What a learner can do afterwards
- Write the same small graph as an adjacency matrix and as an adjacency list
- Say which storage suits a sparse graph and which suits a dense one, with the reason
- Model a real situation, such as a route map, as nodes, edges and weights
1 · Read
A graph is nodes joined by edges, and the edges can be directed and can carry a weight like a distance. You store the same graph two ways: an adjacency matrix, a grid with one row and column per node marking links, or an adjacency list, where each node just names its neighbours.
Take nodes A, B, C, D with edges A to B, A to C, B to D, C to D. Row A of the matrix reads 0, 1, 1, 0 across A, B, C, D. The list entry is shorter: A names B, C. Counting the names in a full list, like A: B, C with B: C and C: none, gives 3 directed edges.
You pick by density. A sparse graph has far fewer edges than possible pairs, so a list wins by storing only real edges. A dense graph joins most pairs, so the matrix grid of marks is more compact. A matrix for n nodes always holds n rows by n columns, so 6 nodes need 36 cells.
You model a route map by turning places into nodes and roads into edges. Ashcombe, Bridgeton and Cliffwood become nodes, and the 5 km and 8 km road lengths become edge weights on the roads joining them.
Matrices grid every pair while lists name neighbours, and density decides the cheaper store.
2 · Watch
Take it off screen
Where it sits
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.