Breadth-first traversal
Level by level with a queue, shortest paths in unweighted graphs, and a breadth-first visit of the mat's zones.
Covers OCR H446 2.3.1 Algorithms · AQA 7517 4.3.1.1 Simple graph-traversal algorithms
Do this lesson in the simulatorPrint it: worksheet (PDF) · answers (PDF) · as a web page
Guide: Stacks and queues explained
Depth-first traversal plunges down one path. Breadth-first traversal spreads out evenly instead: first it visits every neighbour of the start, then every vertex two edges away, then three, like the ripples from a stone dropped in a pond. That one change gives it a property depth-first traversal lacks: it reaches every vertex by the fewest possible edges.
The idea: a queue
Where depth-first traversal uses a stack, breadth-first traversal uses a queue, first in, first out (module A3).
- Mark the start as discovered and add it to the queue.
- While the queue is not empty, take the vertex at the front and visit it. Add each of its neighbours that has not been discovered to the back of the queue, marking it discovered.
A vertex is marked when it joins the queue, not when it leaves. That way no vertex can be waiting in the queue twice.
Here is the same graph as the last lesson, so the two orders can be compared:
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from collections import deque
GRAPH = {"A": ["B", "D"], "B": ["A", "C", "E"], "C": ["B"],
"D": ["A", "E"], "E": ["B", "D", "F"], "F": ["E"]}
def bfs(start):
discovered = [start]
queue = deque([start])
order = []
while len(queue) > 0:
vertex = queue.popleft() # take from the front
order.append(vertex)
for neighbour in GRAPH[vertex]:
if neighbour not in discovered:
discovered.append(neighbour)
queue.append(neighbour) # join at the back
print("took", vertex, " queue now", list(queue))
return order
print(bfs("A"))
A deque (a double-ended queue) takes items from the front quickly with popleft(). A plain list's pop(0) gives the same result, but it shuffles every remaining item along one place, which is slow for a long queue.
| Taken from the front | Added to the back | Queue after |
|---|---|---|
| (start) | A | A |
| A | B, D | B, D |
| B | C, E | D, C, E |
| D | nothing: A and E are already discovered | C, E |
| C | nothing | E |
| E | F | F |
| F | nothing | (empty) |
The order is A, B, D, C, E, F, where depth-first gave A, B, C, E, D, F. B and D, one edge from A, come first; then C and E, two edges away; then F, three.
Shortest paths in an unweighted graph
Because breadth-first traversal works outwards one edge at a time, the first time it discovers a vertex it has found a shortest route to it, counted in edges. Record, for every vertex, the vertex it was discovered from (its parent), and the route can be read backwards from the goal:
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from collections import deque
GRAPH = {"A": ["B", "D"], "B": ["A", "C", "E"], "C": ["B"],
"D": ["A", "E"], "E": ["B", "D", "F"], "F": ["E"]}
def shortest_path(start, goal):
parent = {start: None} # also records what has been discovered
queue = deque([start])
while len(queue) > 0:
vertex = queue.popleft()
for neighbour in GRAPH[vertex]:
if neighbour not in parent:
parent[neighbour] = vertex
queue.append(neighbour)
path = []
v = goal
while v is not None: # follow the parents back to the start
path.append(v)
v = parent[v]
path.reverse()
return path
print(shortest_path("A", "F"))
print(shortest_path("A", "D"))
A to D is now the single edge it should be. The parent links themselves form a tree with the start at its root, and each shortest path is the one route from the root down that tree.
This only works when every edge counts the same. In a weighted graph a route with more edges can cost less, as the warehouse graph showed in lesson A4.1. Dijkstra's algorithm, in module A5, handles weights by replacing the plain queue with a priority queue.
What breadth-first traversal is for
- Shortest paths in unweighted graphs: the fewest moves across a grid, the fewest changes of train, the fewest hops across a network.
- Degrees of separation on a social network: everyone within two connections of a person.
- Finding the nearest of something, such as the closest charging zone to a robot, because nearer vertices are always checked first.
- Web crawlers that visit the pages closest to a starting page before those further away.
Depth-first or breadth-first?
| Depth-first | Breadth-first | |
|---|---|---|
| Data structure | a stack, or recursion | a queue |
| How it explores | along one path as far as possible, then backtracks | level by level outwards from the start |
| Finds shortest paths in an unweighted graph? | no | yes |
| Memory | with recursion, the current path; with its own stack, the path and every neighbour pushed beside it, repeats included | every vertex discovered but not yet visited, which can be a whole level |
| Typical uses | mazes, whether a path exists, cycles, backtracking | shortest routes, nearest item, degrees of separation |
Both visit each reachable vertex once, and with an adjacency list both take time proportional to V + E.
Neither always needs less memory: it depends on the shape of the graph. This cell measures all three versions on two graphs, an open 10 by 10 grid and a tree in which every vertex leads to 4 more, 6 levels deep. For recursion it records the longest path the call stack held; for the other two, the most vertices ever waiting.
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from collections import deque
def grid(n):
"""An n by n grid: each square is joined to the squares above, below and beside it."""
graph = {}
for r in range(n):
for c in range(n):
graph[(r, c)] = [(r + dr, c + dc) for dr, dc in [(-1, 0), (0, -1), (0, 1), (1, 0)]
if 0 <= r + dr < n and 0 <= c + dc < n]
return graph
def tree(branches, levels):
"""A tree in which every vertex leads to `branches` more, `levels` deep."""
graph = {}
level = [()]
for _ in range(levels):
below = []
for v in level:
graph[v] = [v + (i,) for i in range(branches)]
below += graph[v]
level = below
for v in level:
graph[v] = []
return graph
def longest_path(graph, start): # recursive depth-first: the call stack holds the path
visited = set()
def dfs(v, depth):
visited.add(v)
deepest = depth
for n in graph[v]:
if n not in visited:
deepest = max(deepest, dfs(n, depth + 1))
return deepest
return dfs(start, 1)
def biggest_stack(graph, start): # depth-first with a stack of its own, as in lesson A4.3
visited = set()
stack = [start]
biggest = 1
while stack:
v = stack.pop()
if v not in visited:
visited.add(v)
for n in reversed(graph[v]):
if n not in visited:
stack.append(n)
biggest = max(biggest, len(stack))
return biggest
def biggest_queue(graph, start): # breadth-first
discovered = {start}
queue = deque([start])
biggest = 1
while queue:
v = queue.popleft()
for n in graph[v]:
if n not in discovered:
discovered.add(n)
queue.append(n)
biggest = max(biggest, len(queue))
return biggest
for name, graph, start in [("10 by 10 grid", grid(10), (0, 0)),
("tree, 4 branches, 6 levels", tree(4, 6), ())]:
print(name, "with", len(graph), "vertices")
print(" recursive depth-first, longest path:", longest_path(graph, start))
print(" depth-first stack, most waiting: ", biggest_stack(graph, start))
print(" breadth-first queue, most waiting: ", biggest_queue(graph, start))
On the grid, depth-first is the hungry one. The recursive version snakes along each row in turn and never backtracks, so its path grows to all 100 squares, and the stack of its own peaks at 82 because it also holds the squares beside the path, some of them twice. The queue never holds more than 10, one diagonal of the grid. On the tree it is the other way round: the path is never longer than 7 vertices and the stack never holds more than 19, but the queue has to hold the whole bottom level, 4,096 vertices. Breadth-first needs a lot of memory when a level is wide; depth-first needs a lot when a path is long.
The mat as a graph
On this mat, nine zones are the vertices, and a painted track joins two zones wherever the robot is allowed to drive between them. The robot starts in the middle of zone A.
go_to(zone) drives sideways, then forwards or backwards, to the centre of a zone. It works from position(), which gives the robot's position in cm from where it started, so every zone's centre is written relative to A.
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
CENTRE = {"A": (0, 0), "B": (30, 0), "C": (60, 0), "D": (0, -30), "E": (30, -30), "F": (60, -30),
"G": (0, -60), "H": (30, -60), "I": (60, -60)}
def go_to(zone):
x, y = position()
tx, ty = CENTRE[zone]
if tx > x + 1:
right(80, distance=tx - x)
elif tx < x - 1:
left(80, distance=x - tx)
if ty > y + 1:
forward(80, distance=ty - y)
elif ty < y - 1:
backward(80, distance=y - ty)
for zone in ["B", "E", "H"]:
go_to(zone)
print("in zone", zone, "at", position())
Task: a breadth-first visit
The mat's zones and tracks are in GRAPH, an adjacency list with each zone's neighbours in alphabetical order. CENTRE and go_to(zone) are written for you. Write a breadth-first traversal from zone A that uses a queue, taking zones from the front with popleft() or pop(0). Print one line, BFS order: followed by the zones in the order they come off the queue, separated by single spaces. Then drive the robot to each zone in that order with go_to. The robot starts in zone A.
# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()
from collections import deque
# where each zone's centre is, in cm from the start (the robot starts in the middle of zone A)
CENTRE = {"A": (0, 0), "B": (30, 0), "C": (60, 0), "D": (0, -30), "E": (30, -30), "F": (60, -30),
"G": (0, -60), "H": (30, -60), "I": (60, -60)}
GRAPH = {
"A": ["B", "D"],
"B": ["A", "C", "E"],
"C": ["B"],
"D": ["A", "G"],
"E": ["B", "F", "H"],
"F": ["E", "I"],
"G": ["D", "H"],
"H": ["E", "G"],
"I": ["F"],
}
def go_to(zone):
"""Drive sideways then forwards or backwards to the centre of a zone."""
x, y = position()
tx, ty = CENTRE[zone]
if tx > x + 1:
right(80, distance=tx - x)
elif tx < x - 1:
left(80, distance=x - tx)
if ty > y + 1:
forward(80, distance=ty - y)
elif ty < y - 1:
backward(80, distance=y - ty)
Challenges
- Record each zone's distance from A in edges as the traversal discovers it, and print it. Which zone is furthest?
- Traverse the same graph depth-first and drive that order instead. Which drive is longer, and why?
- Find the shortest route from A to I with parent links, and drive only along the tracks to get there.