Breadth-first traversal

Level by level with a queue, shortest paths in unweighted graphs, and a breadth-first visit of the mat's zones.

A4.4Trees and graphsA level30 min

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).

1. Mark the start as discovered and add it to the queue.
2. 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"))

Run this in the simulator

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.

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"))

Run this in the simulator

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?

Both visit each reachable vertex once, and with an adjacency list both take time proportional to V + E.

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())

Run this in the simulator

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

1. Record each zone's distance from A in edges as the traversal discovers it, and print it. Which zone is furthest?
2. Traverse the same graph depth-first and drive that order instead. Which drive is longer, and why?
3. Find the shortest route from A to I with parent links, and drive only along the tracks to get there.