A graph is a set of nodes joined by edges. Road maps, mazes, networks and bridges are all graphs. Three classic questions: how to find the shortest route, how to connect everything as cheaply as possible, and when a walk can cross every edge exactly once.
Every square is a node joined to its four neighbors. Stepping onto ground costs 1 and onto mud costs 5. Draw walls, drag the start or goal, and watch how each algorithm spreads out from the start.
Try this: pick Maze, run Dijkstra, then switch to A* and compare Nodes visited.
| Algorithm | Visited | Steps | Cost |
|---|
Try this: press Compare all to fill every row.
Connect every town using the least total road length. Two greedy algorithms solve it in opposite ways. Kruskal takes the cheapest edges anywhere on the map. Prim grows one tree outward from a single town. Both end with the same total.
How to read this: dots are towns and faint lines are roads you could build. Green roads are the ones each method keeps; the total is their combined length, in the same units as the map.
Try this: press Step and compare which road each side adds.
Kruskal sorts every edge by length and goes down the list. It keeps an edge unless both ends are already connected, because then it would close a loop. Node colors show the separate clusters merging. Rejected edges flash red.
Prim keeps one growing tree. At each step it adds the shortest edge leaving the tree. The amber edges are the candidates it chooses from.
Split the towns into any two groups. The shortest edge crossing between them must belong to some minimum tree. Both algorithms only ever add such an edge, so neither can be beaten.
The people of Königsberg asked whether you could walk through the city crossing each of its seven bridges exactly once. Euler showed in 1736 that you can't, and graph theory started there. Click a district to start, then click glowing bridges to cross them.
How to read this: each circle is a district and each curve is a bridge. The number is how many bridges touch it.
Each time you walk through a district, you arrive on one bridge and leave on another. So any district you only pass through uses its bridges in pairs and needs an even number of them.
Only the start and the end can have an odd count. A walk over every bridge exists only if 0 or 2 districts have an odd degree. Königsberg has 4.