AQA 7517 4.2.4.1: Graphs
The free BugBot lessons that teach this point, a robot to try it on, and the past-paper questions that test it.
What it covers
At GCSE every data structure you met was a line or a table: a list, a two-dimensional array, a record. A lot of data does not have that shape. Roads join towns, web pages link to other pages, and the zones of BugBot's mat are joined wherever the robot can drive from one to the next. A graph is the data structure for relationships like these. This module builds everything on it: trees, traversals, and in the project a robot that plans its own route.
- Vertices and edges
- Undirected, directed and weighted
- A graph in Python: a list of edges
- Degree and the handshake lemma
- Where graphs are used
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A4.1 Graphs Trees and graphs
Vertices and edges; directed, undirected and weighted graphs; degree, the handshake lemma and typical uses. - A4.2 Adjacency matrix and adjacency list Trees and graphs
Two ways to store a graph, and choosing between them for dense and sparse graphs. - A4.8 Project: plan the route Trees and graphs
Model the mat as a graph, find the shortest route with breadth-first search, and drive it.
Try it on a robot
The task from A4.1 Graphs, running here. Change the program and press Run.
The specification is AQA's own document; this page says which of our lessons teach point 4.2.4.1 and is not endorsed by the board.