A First Taste of Algorithms

Lab 5: Dots and Lines

✦ ✦ ✦

Accompanies Chapter 5. The chapter walked graphs three ways with coins and napkins; here the same three walks run on the machine. Two small tools arrive — each because the graph demands it — and a maze of your own design gets solved by ripple, by thread, and then, with one word changed, by each pretending to be the other.

1. A graph in the machine

The chapter’s school, verbatim — a dictionary with one entry per vertex, holding its list of neighbors:

hallways = {
    "gym":       ["lobby"],
    "lobby":     ["gym", "library", "cafeteria"],
    "library":   ["lobby", "lab"],
    "cafeteria": ["lobby", "lab"],
    "lab":       ["library", "cafeteria"],
}

print(hallways["lobby"])

Notice the convention: every edge appears twice (gym lists lobby, lobby lists gym), because a hallway can be walked both ways. Check the dictionary against a drawing of the school — then deliberately desynchronize it (delete "gym" from lobby’s list but keep lobby in gym’s) and hold that thought for Break-it 1.

2. The ripple

BFS, with the queue kept honest in plain sight: the waiting line is a list, and a marker head points at who gets served next. Serving means moving the marker; joining means appending. Nothing is ever deleted — the line keeps its history, which will turn out to be a gift.

One new tool, arriving with its debt: the set. The visited-check must be fast and duplicate-proof; a set is a bag that holds each thing at most once and answers in instantly. Three moves: seen = set(), seen.add(x), x in seen.

def bfs(graph, start):
    queue = [start]
    head = 0
    seen = {start}                      # a set with one thing in it
    dist = {start: 0}                   # the notebook: vertex -> hops
    while head < len(queue):
        here = queue[head]
        head = head + 1                 # serve the front of the line
        for neighbor in graph[here]:
            if neighbor not in seen:
                seen.add(neighbor)
                dist[neighbor] = dist[here] + 1
                queue.append(neighbor)  # join the back of the line
    return dist

print(bfs(hallways, "gym"))

Run it and check every distance against your drawing. Then print queue itself after the run (add a print, or return it too): the line’s history is the rings, in order — read it aloud as “ring 0, ring 1, ring 2” and confirm the bureaucracy did what the chapter promised.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses