AQA 7517 4.3.1.1: Simple graph-traversal algorithms
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
To traverse a graph is to visit every vertex that can be reached from a starting vertex, each exactly once. There are two standard ways to do it, and they differ in which vertex they go to next. Depth-first traversal goes as far as it can along one path before it backs up and tries another. It is how you would explore a maze with a piece of chalk: keep walking, and at a dead end go back to the last junction that still has a way you have not tried.
- The idea
- Recursive depth-first traversal
- With a stack of your own
- What depth-first traversal is for
Or do it in the simulator, with tasks that mark themselves
Lessons that teach it
- A4.3 Depth-first traversal Trees and graphs
Going deep and backtracking, recursively and with a stack; tracing it and what it is used for. - A4.4 Breadth-first traversal Trees and graphs
Level by level with a queue, shortest paths in unweighted graphs, and a breadth-first visit of the mat's zones. - 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.3 Depth-first traversal, 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.3.1.1 and is not endorsed by the board.