A First Taste of Algorithms

Chapter 5: Maps, Mazes, and Networks

✦ ✦ ✦

In which a city’s bridges become dots and lines, and three ways of walking answer almost everything

Königsberg, 1736

The city of Königsberg sat on both banks of a river, plus two islands, the four land masses joined by seven bridges. The townspeople had a standing puzzle: can you take a walk that crosses every bridge exactly once?

They asked Leonhard Euler — already the most prolific mathematician alive — and his first reaction, in a letter, was that the problem “has little connection to mathematics.” Then he solved it, and in solving it he made the connection, founding a field. His move is the reason this chapter exists, so watch it closely. Euler threw the city away. The size of the islands, the length of the bridges, the bends of the river — none of it matters to the question. What matters is only what is connected to what. Each land mass becomes a dot; each bridge a line between two dots. Four dots, seven lines, and the famous old city has become a diagram you can draw on a napkin.

Figure 5.1 — Königsberg and Euler’s napkin: the city, then the same city with everything inessential burned away.

The diagram is called a graph: dots (call them vertices) and connecting lines (edges). And Euler’s answer came straight out of the napkin: such a walk is impossible — every one of the four vertices has an odd number of bridge-ends touching it, and (you will prove this yourself in Practice 2.1, with a counting argument worthy of the name) a walk that crosses every edge once can tolerate at most two odd vertices: its start and its end. Anyone passing through a place must arrive and leave in pairs. The townspeople had been searching for years for something a parity check kills in a minute. Throwing away detail is not laziness; done right, it is the most powerful act in mathematics.

The same picture, everywhere

Once you own the abstraction, you see it daily, because “things, connected to things” is most of the world’s structure:

• your school: rooms as vertices, hallways as edges;
• the subway map (which already is Euler’s napkin — the designers threw away geography for you);
• friendships: people as vertices, an edge per friendship;
• the web: pages as vertices, links as edges — note these edges have a direction;
• and Chapter 4’s closing promise: every dynamic programming table you built was secretly a graph — entries as vertices, an edge from each entry to the entries it consulted. best(14) pointed at best(13), best(7), best(4). You have been drawing graphs since last chapter without the name.

A graph enters Python the way Chapter 4 taught things to enter Python — as a dictionary. One entry per vertex; next to it, the list of its neighbors:

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

That is the entire data structure. The questions, though, are many: can you get from here to there? what is the fewest hallways? the quickest route when hallways have lengths? Remarkably, three walking disciplines — two of them one word apart — answer nearly all of it.

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